Что такое динамическое программирование?

Задачи на динамическое программирование - это такие алгоритмические задачи, в которых каждое новое состояние вы вычисляете через уже корректно посчитанные предыдущие состояния. Простейшими задачами на динамическое программирование являются: "Нахождение суммы на массиве", "Вывод первых N чисел Фибоначчи".