Алгоритмы. Динамическое программирование

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

Чтобы понять, почему без ДП возникают проблемы, рассмотрим классический пример — вычисление чисел Фибоначчи, где каждое следующее число является суммой двух предыдущих. При наивном рекурсивном подходе мы сталкиваемся с катастрофической неэффективностью. Например, при вычислении F(5) дерево вызовов будет выглядеть так: F(5) раскладывается на F(4) и F(3), те в свою очередь на свои составляющие, и в итоге F(3) вычисляется дважды, а F(2) — целых три раза. При росте n количество повторных вычислений взрывается, и сложность алгоритма становится экспоненциальной — O(2ⁿ). Динамическое программирование решает эту проблему кардинально: «посчитал F(3) — запиши, понадобился снова — возьми из записей».

Существует два основных способа реализовать эту идею. Первый способ — мемоизация, или подход «сверху вниз» (top-down). Это всё та же рекурсия, но с использованием блокнота (кэша, обычно словаря). Перед тем как вычислить значение, функция проверяет: «А я это уже считал?». Если ответ найден в словаре, она сразу его возвращает, избегая повторных вычислений. Каждое уникальное значение вычисляется строго один раз.

def fibonacci_dp(n, memo=None):
    """Вычисление чисел Фибоначчи с помощью ДП (мемоизация)."""
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_dp(n - 1, memo) + fibonacci_dp(n - 2, memo)
    return memo[n]

print(fibonacci_dp(10))  # 55

Второй способ — табуляция, или подход «снизу вверх» (bottom-up). Здесь мы отказываемся от рекурсии и начинаем строить решение с самых маленьких, очевидных подзадач, постепенно заполняя таблицу (обычно массив) и двигаясь к искомому результату. Мы точно знаем, что для вычисления следующего значения нам нужны только предыдущие, поэтому просто идем по порядку.

def fibonacci_tabulation(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]

print(fibonacci_tabulation(10))  # 55

Для вычисления числа Фибоначчи мы можем пойти дальше и оптимизировать использование памяти. Так как для текущего значения нужны только два предыдущих, можно хранить лишь их, а не всю таблицу. Это снижает затраты памяти с O(n) до O(1).

def fibonacci_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return prev1

print(fibonacci_optimized(10))  # 55