- Динамическое программирование — метод решения задач путем составления последовательности из подзадач:
- первая подзадача имеет простое решение;
- последний элемент этой последовательности — это исходная задача;
- каждая подзадача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами.
- Этапы решения задачи методом динамического программирования:
- разбиение задачи на подзадачи;
- построение рекуррентной формулы для вычисления значения функции;
- вычисление значения функции для всех подзадач;
- восстановление структуры оптимального ответа.