Динамическое программирование (ДП) решает каждую повторяющуюся подзадачу один раз и запоминает ответ. Экспоненциальная рекурсия превращается в полиномиальное заполнение таблицы.
Когда работает ДП
- Оптимальная подструктура: оптимальный ответ большой задачи строится из оптимальных ответов меньших.
- Перекрывающиеся подзадачи: одна и та же маленькая задача возникает снова и снова.
В «разделяй и властвуй» части независимы, а здесь повторяются. От жадного алгоритма ДП отличается тем, что учитывает все ответы подзадач и не требует доказательства безопасности локального выбора.
Наивная рекурсия экспоненциальна
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(20), calls)
calls = 0
fib(25)
print("fib(25) calls:", calls)fib(20) делает 21 891 вызов, а fib(25) — 242 785: примерно O(1.6^n).
