Рекурсия сводит задачу к более простой версии самой себя. Иногда это работает прекрасно, а иногда программа намертво зависает на входе из сорока элементов. Разберём, почему так выходит и как это чинится — приём называется динамическим программированием, и за громким названием прячется довольно простая мысль.
Проблема: одно и то же считается многократно
Классический пример — числа Фибоначчи, где каждое следующее равно сумме двух предыдущих:
static long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
Код точно повторяет определение и совершенно нерабочий: fib(50) считается минутами. Причина видна, если нарисовать дерево вызовов. Чтобы посчитать fib(5), нужны fib(4) и fib(3). Но fib(4) внутри себя снова считает fib(3). А fib(3) — снова fib(2). И так далее: одни и те же значения пересчитываются по многу раз, а число вызовов растёт примерно вдвое с каждым шагом.
Ключевое наблюдение: подзадачи перекрываются. Их на самом деле мало — всего n штук, — но наивная рекурсия не помнит, что уже считала.
Мемоизация: просто запомнить
Самое прямое лечение — завести блокнот и записывать туда посчитанное:
static long fib(int n, Map<Integer, Long> memo) {
if (n <= 1) return n;
Long known = memo.get(n);
if (known != null) return known;
long value = fib(n - 1, memo) + fib(n - 2, memo);
memo.put(n, value);
return value;
}
Изменилось три строки, а сложность упала с почти двух в степени n до O(n): каждое значение считается ровно один раз, дальше берётся из блокнота. Такой подход называют «сверху вниз» — мы по-прежнему идём от большой задачи к маленьким, просто перестаём повторяться.
Таблица: снизу вверх
Если подзадачи можно упорядочить так, чтобы каждая опиралась только на уже посчитанные, рекурсия вообще не нужна — достаточно заполнить таблицу по порядку:
static long fib(int n) {
if (n <= 1) return n;
long[] dp = new long[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
Это «снизу вверх». Работает быстрее (нет накладных расходов на вызовы) и не рискует переполнить стек вызовов на большой глубине. Плата — надо самому придумать правильный порядок заполнения.
Состояние и переход
Чтобы применить приём к незнакомой задаче, отвечают на два вопроса.
Что такое состояние? Это набор параметров, полностью описывающий подзадачу. Для Фибоначчи состояние — одно число i. Для рюкзака — пара «сколько товаров рассмотрели» и «сколько места осталось».
Каков переход? Это формула, выражающая ответ для состояния через ответы для меньших состояний. Плюс базовые случаи — состояния с готовым ответом.
Возьмём задачу: вдоль дороги стоят склады с выручкой, забирать с двух соседних подряд нельзя, нужна наибольшая сумма. Состояние — номер склада. Переход: на каждом складе выбор из двух — пропустить его (тогда ответ такой же, как на предыдущем) или взять (тогда прибавляем к ответу двухшаговой давности, ведь соседний брать было нельзя).
static int bestPickup(int[] revenue) {
int skip = 0;
int take = 0;
for (int money : revenue) {
int next = Math.max(skip, take);
take = skip + money;
skip = next;
}
return Math.max(skip, take);
}
Здесь видна частая оптимизация: раз каждое состояние зависит только от двух предыдущих, вся таблица сворачивается в две переменные. Память — O(1) вместо O(N).
Два измерения: рюкзак
Когда состояние описывается парой параметров, таблица становится двумерной. Классика — задача о рюкзаке: сумка выдерживает capacity килограммов, у каждого товара есть вес и цена, товар кладём целиком или не кладём.
Состояние — «рассмотрели первые i товаров, осталось left места», ответ — наибольшая цена. Переход: либо не берём товар (ответ как для i-1), либо берём (цена товара плюс ответ для i-1 с уменьшенным местом).
Таблицу тоже можно свернуть — до одной строки, но с важной тонкостью:
static int bestParcel(int[] weights, int[] prices, int capacity) {
int[] best = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (int left = capacity; left >= weights[i]; left--) {
best[left] = Math.max(best[left], best[left - weights[i]] + prices[i]);
}
}
return best[capacity];
}
Внутренний цикл идёт справа налево, и это не стилистический выбор. При проходе слева направо ячейка best[left - weight] уже содержала бы результат с текущим товаром, и товар попал бы в сумку несколько раз — получилась бы другая задача, где предметы можно брать повторно.
Сложность — O(N · capacity). Это не полиномиальная зависимость от размера входа (число capacity записывается логарифмом цифр), поэтому на очень больших вместимостях приём перестаёт спасать.
Когда приём применим
Нужны два свойства одновременно:
- перекрывающиеся подзадачи — наивная рекурсия решает одно и то же по многу раз; если подзадачи все разные, запоминать нечего;
- оптимальная подструктура — ответ для задачи собирается из ответов для меньших подзадач; если оптимальный ответ может требовать неоптимального решения подзадачи, формула перехода будет неверной.
Признаки в условии: спрашивают количество способов, минимум или максимум по всем вариантам, а наивное решение — полный перебор с ветвлением «взять или не взять».
Если же на каждом шаге очевидно, что брать, и это никогда не приходится пересматривать, — задача проще, и хватит жадного прохода без всякой таблицы.
Коротко
- Динамическое программирование — это перебор, который не повторяет уже сделанную работу.
- Условие применимости: подзадачи перекрываются, а ответ собирается из ответов на меньшие подзадачи.
- Мемоизация («сверху вниз») — рекурсия плюс блокнот с посчитанным; меняется три строки, сложность падает драматически.
- Таблица («снизу вверх») — заполнение по порядку без рекурсии: быстрее и без риска переполнить стек вызовов.
- Проектирование сводится к двум вопросам: что такое состояние и каков переход между состояниями.
- Если состояние зависит от пары предыдущих, таблица сворачивается до нескольких переменных — память O(1).
- В свёрнутом рюкзаке направление внутреннего цикла определяет, можно ли брать предмет повторно.
Дальше — перебор с отсечением: что делать, когда нужны не число, а сами варианты.