Динамическое программирование: мемоизация и табуляция

Динамическое программирование: мемоизация (сверху вниз) и табуляция (снизу вверх) на примере чисел Фибоначчи — кэширование подзадач для устранения дублирующихся вычислений.

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

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

При наивном вычислении fib(5) одни и те же значения вычисляются многократно:

call_count = [0]

def fib_naive(n):
    call_count[0] += 1
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

result = fib_naive(10)
print(f"fib(10) = {result}, вызовов функции: {call_count[0]}")

Вывод:

fib(10) = 55, вызовов функции: 177

Для fib(30) это уже более миллиона вызовов. Проблема — повторные вычисления одних и тех же подзадач.

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

Мемоизация — рекурсия + кэш. Перед вычислением проверяем: не считали ли уже? Если да — возвращаем кэшированный результат.

def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

print(f"fib(10) = {fib_memo(10)}")
print(f"fib(30) = {fib_memo(30)}")
print(f"fib(50) = {fib_memo(50)}")

Вывод:

fib(10) = 55
fib(30) = 832040
fib(50) = 12586269025

В Python можно использовать декоратор @functools.lru_cache — он сделает мемоизацию автоматически.

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

Табуляция — итеративный подход: заполняем таблицу от базовых случаев к искомому значению. Никакой рекурсии, никакого стека вызовов.

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

for i in [5, 10, 20]:
    print(f"fib({i}) = {fib_tab(i)}")

Вывод:

fib(5) = 5
fib(10) = 55
fib(20) = 6765

Сравнение подходов

Мемоизацию проще написать (добавляем кэш к рекурсии). Табуляция часто быстрее на практике — нет накладных расходов на вызов функций и нет риска переполнения стека.

Коротко

• DP = рекурсия с кэшированием подзадач; каждая подзадача решается ровно один раз.
• Мемоизация — рекурсия + кэш-словарь (сверху вниз).
• Табуляция — итерация снизу вверх; безопаснее для глубоких задач.
• Оба метода снижают сложность Фибоначчи с O(2ⁿ) до O(n).