Что такое динамика

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

Название историческое и ничего не объясняет: Ричард Беллман придумал его в 1950-х, когда нужно было название, под которое дадут финансирование. Слово «программирование» здесь означает «планирование», а не написание кода.

Полезнее другое определение, рабочее.

Четыре вопроса

Решить задачу динамикой — значит ответить на четыре вопроса. Ответы можно записать на бумаге до того, как написана первая строка кода.

1. Состояние. Что мы считаем? Какой набор чисел полностью описывает подзадачу?
2. Переход. Как выразить состояние через уже посчитанные?
3. База. Какие состояния известны сразу, без пересчёта?
4. Порядок. В каком порядке считать, чтобы при пересчёте всё нужное уже было готово?

Дальше — механическая работа. Почти все ошибки в динамике сидят в том, что на один из четырёх вопросов ответили небрежно.

Пример целиком

Лестница из $n$ ступеней, за один шаг разрешается подняться на одну или на две. Сколькими способами можно подняться?

Состояние: $d[i]$ — число способов дойти до ступени $i$.

Переход: на ступень $i$ мы попали либо с $i - 1$, либо с $i - 2$, и эти множества способов не пересекаются — последний шаг у них разный. Значит,

$$d[i] = d[i-1] + d[i-2]$$

База: $d[0] = 1$ — стоять на земле можно одним способом, ничего не делая. $d[1] = 1$.

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

vector<long long> d(n + 1);
d[0] = 1;
d[1] = 1;
for (int i = 2; i <= n; i++) d[i] = d[i - 1] + d[i - 2];
cout << d[n];

Проверено: для $n$ от 0 до 22 совпадает с перебором всех последовательностей шагов. Для тридцати ступеней ответ 1 346 269.

База «$d[0] = 1$» смущает почти всех. Проверка простая: посчитайте $d[2]$ руками — способов ровно два (1+1 и 2), и формула даёт $d[1] + d[0] = 1 + 1 = 2$. Если бы $d[0]$ был нулём, вышло бы 1. База не угадывается, она проверяется на маленьком случае.

Когда динамика вообще применима

Нужны два свойства. Оба стоит проверять до написания кода, а не после.

Подзадачи повторяются. Если бы каждая подзадача встречалась один раз, запоминать было бы нечего — это обычная рекурсия «разделяй и властвуй», как в сортировке слиянием. Динамика окупается ровно потому, что $d[i-2]$ нужен и для $d[i]$, и для $d[i-1]$.

Ответ подзадачи не зависит от того, как мы в неё пришли. Число способов подняться на ступень 5 одинаково независимо от того, что было раньше. Это свойство и позволяет хранить одно число на состояние.

Второе свойство ломается чаще, чем кажется. Если в задаче есть ограничение вида «нельзя дважды подряд делать одно и то же», то состояния «ступень 5» недостаточно — надо знать ещё и последний шаг. Лечится это не отказом от динамики, а расширением состояния: $d[i][j]$, где $j$ — каким шагом пришли.

Что даёт запоминание

Та же формула без массива — обычная рекурсия:

long long ways(int n) {
    if (n <= 1) return 1;
    return ways(n - 1) + ways(n - 2);
}

Она верна и безнадёжно медленна: дерево вызовов растёт как $\varphi^n \approx 1{,}618^n$.

Разница между рекурсией и динамикой видна на картинке. Рекурсия обходит дерево вызовов, где ways(3) встречается дважды, ways(2) — трижды, и каждое вхождение считается заново:

flowchart TD
    A["ways(5)"] --> B["ways(4)"]
    A --> C["ways(3)"]
    B --> D["ways(3)"]
    B --> E["ways(2)"]
    C --> F["ways(2)"]
    C --> G["ways(1)"]
    D --> H["ways(2)"]
    D --> I["ways(1)"]

Динамика считает тот же набор состояний, но каждое по одному разу — дерево склеивается в граф, где повторов нет:

flowchart RL
    W1["d[1]"] --> W3["d[3]"]
    W2["d[2]"] --> W3
    W2 --> W4["d[4]"]
    W3 --> W4
    W3 --> W5["d[5]"]
    W4 --> W5

Вершин здесь $n$, стрелок — по две на вершину. Это и есть источник линейного времени: работа равна числу стрелок в графе состояний, а не числу путей по нему.

Замер на нашем сервере, g++ -O2:

$n$	рекурсия	динамика
30	1 мс	0,0006 мс
35	8 мс	0,001 мс
40	76 мс	0,0007 мс
45	913 мс	0,0008 мс

Каждые пять ступеней время рекурсии растёт примерно в одиннадцать раз; у динамики оно не растёт вовсе — на таких $n$ всё тонет в накладных расходах. К пятидесяти ступеням рекурсия выйдет за десять секунд, а динамика будет считать столько же, сколько считала.

Написать рекурсию и добавить к ней массив ответов — это мемоизация, и она даёт ту же асимптотику. Разница между ней и циклом — в константе и в стеке, об этом отдельная статья.

Сколько стоит динамика

Считается в одно действие:

$$\text{время} = (\text{число состояний}) \times (\text{стоимость одного перехода})$$

Для лестницы: $n$ состояний, переход в два сложения — $O(n)$. Для рюкзака: $n \cdot W$ состояний, переход за $O(1)$ — $O(nW)$. Для динамики по подотрезкам: $n^2$ состояний, переход перебирает точку деления — $O(n^3)$.

Это же произведение — способ понять по ограничениям, ждут ли от вас динамику и какую. Если в условии $n \le 100$ и $W \le 10^5$, перемножьте: $10^7$ — как раз таблица рюкзака. Если $n \le 500$ — вероятна кубическая динамика по подотрезкам. Если $n \le 20$ — маски.

Динамика и жадность

Оба приёма строят ответ по шагам. Разница в том, что жадность на каждом шаге выбирает вариант окончательно, а динамика хранит ответ для всех вариантов сразу.

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

Классическая пара, где видно границу, — непрерывный и дискретный рюкзак: одно слово в условии, и жадность перестаёт работать.