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

Динамическое программирование пугает названием, а по сути это одна честная идея: не считать одно и то же дважды. Ниже — полная теория из курса «Кружок 102».

Зачем это нужно

Представь, что тебе нужно посчитать число Фибоначчи F(40) обычной рекурсией: fib(n) = fib(n-1) + fib(n-2). Код выглядит невинно, но если запустить его на C++, он будет думать несколько секунд, а на F(50) вообще не дождёшься ответа. Причина в том, что рекурсия пересчитывает одни и те же значения снова и снова: fib(5) вызывает fib(4) и fib(3), а fib(4) внутри себя опять вызывает fib(3), и так по всему дереву вызовов — оно разрастается экспоненциально, хотя различных подзадач у нас всего n+1: fib(0), fib(1), …, fib(n).

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

Чтобы ДП вообще было применимо, у задачи должны быть два свойства.

Оптимальная подструктура — ответ на большую задачу собирается из ответов на меньшие подзадачи того же типа. Например, самый дешёвый способ добраться до i-й ступеньки лесенки — это самый дешёвый способ добраться до одной из предыдущих ступенек плюс цена самой i-й. Если бы оптимальный путь до i-й ступеньки не проходил через оптимальный путь до предшественника, мы могли бы взять этот неоптимальный кусок и заменить его оптимальным, получив путь ещё дешевле — противоречие. Именно это рассуждение «от противного» и доказывает корректность почти всех ДП.

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

Два способа реализации: сверху и снизу

Сверху вниз (мемоизация). Пишем ту же рекурсию, что и раньше, но заводим массив (или хеш-таблицу) memo, где memo[state] хранит уже посчитанный ответ, а изначально там лежит метка «не вычислено». В начале функции проверяем: если ответ для этого состояния уже есть — сразу возвращаем его, не углубляясь в рекурсию.

long long memo[50];
bool computed[50];

long long fib(int n) {
    if (n <= 1) return n;
    if (computed[n]) return memo[n];
    computed[n] = true;
    return memo[n] = fib(n - 1) + fib(n - 2);
}

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

long long fib(int n) {
    vector<long long> dp(n + 1);
    dp[0] = 0;
    if (n >= 1) dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Оба варианта дают одинаковую асимптотику и по сути решают одни и те же подзадачи. Разница практическая. Мемоизация проще писать, когда граф подзадач сложный и неочевидно, в каком порядке их считать — рекурсия сама разберётся, в каком порядке вызывать. Табуляция обычно работает быстрее (нет накладных расходов на рекурсивные вызовы и риска переполнить стек на больших n) и её легче ужать по памяти — например, в Фибоначчи нам на самом деле не нужен весь массив dp, а достаточно хранить последние два значения:

long long fib(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return a;
}

Такое сжатие памяти — распространённый приём: если dp[i] зависит только от dp[i-1] (или от последних k слоёв), можно не хранить всю таблицу целиком, а катать вперёд пару-тройку переменных.

Как думать над ДП-задачей

Самое сложное в ДП — не реализация, а придумывание состояния: что именно означает dp[...] и какая между состояниями связь (переход). Полезная последовательность рассуждений:

1. Сформулировать, что такое подзадача — обычно это «ответ на исходную задачу, но для префикса длины i» или «...для меньшего числа n», или «...с ограничением по какому-то ресурсу k».
2. Понять, из каких меньших подзадач собирается решение текущей — это и есть переход (рекуррентная формула).
3. Определить базовые случаи — подзадачи, которые считаются напрямую, без рекурсии.
4. Понять порядок вычисления: если переход у dp[i] использует только dp[j] при j < i, можно спокойно считать по возрастанию i.

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

Вот тут и виден весь скелет ДП. Состояние: пусть dp[i] — минимальная стоимость, чтобы оказаться на i-й ступеньке. Переход: на i-ю ступеньку можно попасть либо с (i-1)-й, либо с (i-2)-й, а платить в любом случае придётся цену cost[i] самой i-й ступеньки. Значит из двух вариантов выбираем дешёвый:

dp[i] = min(dp[i-1], dp[i-2]) + cost[i].

Базовые случаи: dp[0] = cost[0] (на первую ступеньку встали и заплатили), dp[1] = cost[1] (на вторую можно шагнуть сразу снизу, минуя первую). Дальше идём циклом по возрастанию i — как раз потому, что dp[i] смотрит только назад, на dp[i-1] и dp[i-2].

long long cheapestStairs(vector<long long>& cost) {
    int n = cost.size();
    if (n == 0) return 0;
    if (n == 1) return cost[0];
    vector<long long> dp(n);
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < n; i++)
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    return dp[n - 1];
}

Обрати внимание: это ровно та же структура, что у Фибоначчи, — состояний O(n), переход O(1), каждое dp[i] зависит от двух предыдущих. Разница только в том, что вместо сложения мы берём min и добавляем цену. Почти все простые одномерные ДП устроены так же: линейный массив dp, и dp[i] собирается из нескольких соседних значений слева.

> Врезка. А что, если ходить можно не по прямой линии ступенек, а по клеткам таблицы — вправо и вниз? Тогда состояние становится двумерным: dp[i][j]. Такое двумерное ДП (пути на сетке, треугольники и таблицы) мы увидим в следующих темах — идея та же, просто индексов у состояния два.

Оценка сложности

Время работы ДП почти всегда считается по формуле

время = (число различных состояний) × (время на один переход).

В Фибоначчи и в лесенке состояний O(n), переход O(1) — итого O(n). Если бы переход требовал перебора, скажем, ещё одного индекса от 0 до k, время выросло бы до O(n · k). Эта формула — первое, что стоит прикидывать: часто именно она подсказывает, полезут ли лимиты по времени, и какого рода состояние вообще можно себе позволить (если n ≤ 10⁵, состояние с двумя индексами до n уже даст 10¹⁰ — не пройдёт).

Память в bottom-up варианте (снизу вверх) равна числу состояний (размеру таблицы dp), но её часто можно уменьшить, если понятно, что для перехода нужен не весь массив, а только последний (или последние несколько) слой — как в примере с Фибоначчи выше, где O(n) памяти ужалось до O(1). Ровно так же можно ужать и лесенку: раз dp[i] смотрит только на два предыдущих значения, хватит двух переменных вместо всего массива.

Ещё один пример: сумма без соседних элементов

Классическая разминочная задача: дан массив чисел, нужно выбрать подмножество элементов с максимальной суммой так, чтобы никакие два выбранных элемента не стояли рядом (задача «домушника», не подходящего к соседним домам, чтобы не сработала сигнализация). Пусть dp[i] — максимальная сумма, которую можно набрать, рассматривая только первые i элементов. Для i-го элемента есть ровно два варианта: не брать его — тогда ответ такой же, как для первых i-1 элементов, или взять его — тогда предыдущий элемент брать нельзя, и ответ равен a[i] + dp[i-2]. Берём максимум из двух вариантов:

dp[i] = max(dp[i-1], dp[i-2] + a[i]).

long long maxSumNoAdjacent(vector<long long>& a) {
    int n = a.size();
    if (n == 0) return 0;
    vector<long long> dp(n + 1, 0);   // dp[i] — ответ для префикса длины i
    dp[1] = a[0];
    for (int i = 2; i <= n; i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + a[i - 1]);
    return dp[n];
}

Здесь важна одна тонкость: мы всегда можем ничего не брать и получить сумму 0 (пустое подмножество). Поэтому если все числа в массиве отрицательные, правильный ответ — именно 0: любой ненулевой элемент только ухудшит сумму. База dp(n + 1, 0) и guard if (n == 0) return 0; как раз это и обеспечивают — dp[0] = 0 соответствует «ничего не выбрали».

Эта задача — хороший шаблон: почти любое простое одномерное ДП сводится к вопросу «взять текущий элемент или нет», где выбор одного из вариантов «дёргает» разные предыдущие состояния.

Ещё один частый паттерн в задачах этой темы — минимальное число монет (coin change): даны номиналы монет и сумма, надо набрать сумму наименьшим числом монет. Состояние тут — dp[s] = минимальное число монет, чтобы набрать сумму s, а переход перебирает, какую монету положить последней: dp[s] = min(dp[s - coin] + 1) по всем номиналам coin. Идея всё та же — «ответ для s через ответы для меньших сумм», просто переход перебирает несколько вариантов вместо двух.

Восстановление ответа

Часто в задаче нужен не только числовой ответ (сумма, количество способов), но и сама последовательность выборов — например, какие именно элементы взяли. Для этого во время заполнения dp заводят параллельный массив choice[i] (или from[i]), где записывают, какой из вариантов перехода оказался лучше. После того как таблица заполнена, идут от последнего состояния к первому, читая по этому массиву, какое решение было принято на каждом шаге, и восстанавливают ответ в обратном порядке.

pair<long long, vector<long long>> maxSumNoAdjacentWithSet(vector<long long>& a) {
    int n = a.size();
    vector<long long> dp(n + 1, 0);
    vector<bool> take(n + 1, false);
    if (n >= 1) { dp[1] = a[0]; take[1] = true; }
    for (int i = 2; i <= n; i++) {
        if (dp[i - 1] >= dp[i - 2] + a[i - 1]) {
            dp[i] = dp[i - 1];
        } else {
            dp[i] = dp[i - 2] + a[i - 1];
            take[i] = true;
        }
    }

    vector<long long> chosen;
    int i = n;
    while (i >= 1) {
        if (take[i]) {
            chosen.push_back(a[i - 1]);
            i -= 2;
        } else {
            i -= 1;
        }
    }
    reverse(chosen.begin(), chosen.end());
    return {dp[n], chosen};
}

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

На что смотреть при разборе новой задачи

Когда видишь незнакомую задачу и подозреваешь, что она решается ДП, полезно спросить себя: можно ли описать состояние небольшим числом параметров (на этой теме — обычно один индекс), выражается ли ответ для этого состояния через ответы для «меньших» состояний, и не пересчитываются ли одинаковые подзадачи много раз при наивном переборе. Если на все три вопроса ответ «да» — почти наверняка перед тобой ДП, и дальше остаётся только аккуратно выписать переход и базовые случаи, а мемоизация или табуляция сделают всё остальное за O(число состояний × время перехода) вместо экспоненциального перебора.