Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путем разбиения их на простые подзадачи.
Среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.

С помощью динамического программирования решаются задачи, которые требуют полный перебор вариантов и звучат как:

• «Посчитайте количество вариантов…»
• «Как оптимально распределить…»
• «Найдите оптимальный маршрут…»

Задача № 22     

Перейти к решению