Динамическое программирование: основы и идея мемоизации

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

Перекрывающиеся подзадачи

Возьмём классическую рекуррентную функцию для чисел Фибоначчи:

$F(n) = F(n-1) + F(n-2), \qquad F(0) = 0,\; F(1) = 1.$

Если реализовать её "в лоб" - обычной рекурсией без запоминания, - вызов $F(5)$ разворачивается в дерево вызовов, где $F(3)$ считается дважды, а $F(2)$ - трижды. Чем больше $n$, тем сильнее раздувается дерево: одни и те же подзадачи пересчитываются заново на каждом пути к ним.

Рассчитать для своей задачи

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

Оптимальная подструктура

Второе условие - оптимальная подструктура: решение задачи размера $n$ можно собрать из решений задач меньшего размера без пересмотра уже принятых решений. Для чисел Фибоначчи это очевидно: $F(n)$ полностью определяется значениями $F(n-1)$ и $F(n-2)$, и ничего кроме этих двух чисел для перехода не нужно. То же свойство держится в задаче о рюкзаке, в подсчёте числа путей на сетке, в поиске наибольшей возрастающей подпоследовательности - везде ответ на шаге $i$ выражается через уже посчитанные ответы на шагах меньше $i$.

Если оба условия выполнены - подзадачи перекрываются и решение раскладывается на подзадачи - задачу можно решать методом ДП одним из двух способов: мемоизацией или табуляцией.

Мемоизация: нисходящий подход

Мемоизация - это та же рекурсия, но с кэшем. Перед тем как считать $F(n)$, функция проверяет, нет ли уже готового ответа в таблице (обычно массиве или хэш-таблице). Если есть - результат берётся из кэша за $O(1)$. Если нет - результат считается рекурсивно и сохраняется перед возвратом.

Псевдокод мемоизированного Фибоначчи:

memo = {}
function fib(n):
    if n <= 1: return n
    if n in memo: return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

Каждое значение $F(0), F(1), \ldots, F(n)$ вычисляется не более одного раза - именно это устраняет экспоненциальный рост наивной рекурсии.

Табуляция: восходящий подход

Табуляция решает подзадачи не сверху вниз, а снизу вверх: сначала заполняются базовые случаи, потом - шаг за шагом - все промежуточные значения, пока не будет получен ответ для $n$.

Рассчитать для своей задачи

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

$$dp[0] = 0,\qquad dp[1] = 1,\qquad dp[i] = dp[i-1] + dp[i-2]\ \text{для } i \ge 2.$$

Ответ $F(n)$ - это просто $dp[n]$ после того, как таблица заполнена до индекса $n$. У табуляции нет накладных расходов на рекурсию (стек вызовов не растёт), поэтому на практике она обычно немного быстрее мемоизации при той же асимптотике.

Сравнение сложности: рекурсия против ДП

Число вызовов функции в наивной рекурсии для $F(n)$ подчиняется формуле $C(n) = 2\,F(n+1) - 1$ и растёт экспоненциально, примерно как $\varphi^n$, где $\varphi \approx 1{,}618$ - золотое сечение. Табуляция же заполняет ровно $n+1$ ячеек - по одной на каждую подзадачу, то есть её сложность линейна: $O(n)$.

Рассчитать для своей задачи

Разница ощутима уже на небольших $n$. При $n = 10$ наивная рекурсия делает $C(10) = 177$ вызовов против $11$ ячеек табуляции - разрыв около 16 раз. При $n = 20$ это уже $21\,891$ вызов против $21$ ячейки - разрыв больше тысячи раз. При $n = 35$ наивная рекурсия делает почти $30$ миллионов вызовов, а табуляции хватает $36$ шагов. Экспонента против линейной функции - вот что в действительности решает мемоизация или табуляция.

Как распознать задачу на ДП

Прежде чем писать код, стоит проверить задачу по короткому чек-листу:

1. Есть ли выбор на каждом шаге? (взять предмет или нет, сделать шаг вправо или вниз, включить элемент в подпоследовательность или пропустить).
2. Можно ли задачу для размера $n$ свести к задачам меньшего размера без пересмотра уже принятых решений (оптимальная подструктура)?
3. Повторяются ли одни и те же подзадачи при разных путях рекурсии (перекрывающиеся подзадачи)? Если каждая подзадача встречается ровно один раз - запоминать нечего, это обычная рекурсия или разделяй-и-властвуй (как быстрая сортировка), а не ДП.
4. Можно ли описать состояние подзадачи коротким набором параметров (индекс, остаток веса, длина префикса) - именно эти параметры станут измерениями таблицы $dp$.

Если на все четыре вопроса ответ "да" - перед вами задача на ДП, и дальше нужно только определить рекуррентное соотношение и порядок заполнения таблицы, как в задаче о рюкзаке, в подсчёте путей на сетке или в поиске наибольшей возрастающей подпоследовательности - структура рассуждения везде одна и та же.

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

• Мемоизация без базовых случаев. Если функция не проверяет условие остановки перед обращением к кэшу, рекурсия уходит в бесконечную глубину и переполняет стек.
• Табуляция в неправильном порядке. Ячейка $dp[i]$ должна вычисляться после всех ячеек, от которых она зависит; перепутанный порядок обхода даёт обращение к ещё не заполненным значениям.
• Путаница между мемоизацией и табуляцией. Это два разных способа реализации одной и той же идеи - запоминания результатов, - а не два разных алгоритма с разной асимптотикой.
• Попытка сэкономить память без проверки зависимостей. Если $dp[i]$ зависит только от $dp[i-1]$ и $dp[i-2]$, всю таблицу хранить не нужно - достаточно двух последних значений; но это оптимизация памяти, а не самого метода.
• Игнорирование переполнения. Числа Фибоначчи растут экспоненциально, и уже при $n$ около 90 значение $F(n)$ выходит за пределы 64-битного целого - нужны big-integer типы.

FAQ

Чем мемоизация отличается от табуляции? Обе реализуют одну идею - не пересчитывать подзадачи повторно. Мемоизация делает это "сверху вниз" через рекурсию с кэшем, табуляция - "снизу вверх" через явный цикл по таблице. Асимптотическая сложность обычно совпадает, табуляция чуть быстрее на практике за счёт отсутствия рекурсии.

Всегда ли динамическое программирование быстрее рекурсии? Быстрее наивной рекурсии без запоминания - да, если в задаче есть перекрывающиеся подзадачи. Если подзадачи не повторяются (как в классической быстрой сортировке), запоминать нечего, и ДП не даёт выигрыша.

Как выбрать, какие параметры сделать измерениями таблицы dp? Нужно найти минимальный набор величин, которые полностью описывают состояние подзадачи - обычно это индекс позиции плюс один-два дополнительных параметра (остаток ресурса, последний выбранный элемент). Если добавить лишний параметр, таблица разрастётся без необходимости; если параметра не хватит, переход не будет корректным.

Коротко

Динамическое программирование применимо там, где у задачи есть перекрывающиеся подзадачи и оптимальная подструктура. Мемоизация запоминает результаты рекурсии "сверху вниз", табуляция строит таблицу ответов "снизу вверх" - обе реализации сводят экспоненциальную сложность наивной рекурсии к линейной или полиномиальной. На числах Фибоначчи разница видна уже при небольших $n$: наивная рекурсия делает тысячи и миллионы лишних вызовов там, где табуляции хватает одной проходки по таблице.