Введение в динамическое программирование

Если рекурсия пересчитывает одно и то же — её спасает мемоизация.

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

Проблема наивной рекурсии

Числа Фибоначчи: fib(n) = fib(n-1) + fib(n-2). Наивная рекурсия пересчитывает одни и те же значения экспоненциальное число раз — это O(2^n).

def fib_slow(n):
    if n < 2:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

print(fib_slow(10))
print(fib_slow(20))

Вывод:

55
6765

Мемоизация: сверху вниз

Запоминаем уже посчитанные значения в кэше. Тогда каждое fib(k) вычисляется один раз — O(n).

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))
print(fib(50))

Вывод:

55
12586269025

Табуляция: снизу вверх

Можно обойтись без рекурсии: заполняем таблицу от базовых случаев к ответу. А если хранить только два последних значения — память O(1).

def fib_iter(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

print(fib_iter(10))
print(fib_iter(50))

Вывод:

55
12586269025

Как работает под капотом

DP применимо при двух признаках: перекрывающиеся подзадачи (одни и те же вычисления повторяются) и оптимальная подструктура (ответ строится из ответов подзадач). Мемоизация (top-down) кэширует результаты рекурсии. Табуляция (bottom-up) заполняет таблицу итеративно, избегая рекурсии и её накладных расходов. Часто можно ужать память, храня лишь несколько последних состояний — как в fib_iter.

Частые ошибки

Не заметить перекрытие подзадач и оставить O(2^n) рекурсию.
Неверно задать базовые случаи — вся таблица «поедет».
Хранить всю таблицу, когда нужны лишь последние состояния — лишняя память.

Итог

DP убирает повторные вычисления перекрывающихся подзадач.
Top-down — рекурсия с мемоизацией; bottom-up — заполнение таблицы.
Память часто можно ужать до нескольких последних состояний.