Что такое динамическое программирование? Классическая задача — числа Фибоначчи

Динамическое программирование — подход, при котором задачу разбивают на повторяющиеся подзадачи и сохраняют их решения, чтобы не вычислять одно и то же несколько раз. На числах Фибоначчи это позволяет улучшить наивную рекурсию с O(2ⁿ) до O(n).