Динамическое программирование (DP)

Предпосылки: рекурсия, оценка сложности в O(…), массив (индексация), хеш-таблица (значение по ключу), базовое чтение Ruby (методы, блоки, массивы и хеши).

Числа Фибоначчи задаются через самих себя: fib(n) = fib(n - 1) + fib(n - 2), а fib(0) = 0, fib(1) = 1. Запишем это определение в лоб рекурсией и попросим fib(5). Чтобы получить fib(5), нужны fib(4) и fib(3). Чтобы получить fib(4) — снова fib(3) и fib(2). fib(3) уже считался в первой ветке, но рекурсия об этом не знает и считает заново:

fib(5)
+- fib(4)
|  +- fib(3)
|  |  +- fib(2)
|  |  +- fib(1)
|  +- fib(2)   <- повтор
+- fib(3)      <- повтор

Чем больше n, тем хуже: дерево вызовов ветвится надвое на каждом шаге, и число пересчётов удваивается. Время растёт как 2^n — экспоненциально, и fib(50) рекурсией в лоб уже не дождаться. При этом разных значений всего n + 1: fib(0), fib(1), …, fib(n). Вся работа уходит на повторное вычисление того, что уже было посчитано.

Отсюда вся идея: если одна и та же подзадача встречается много раз, её ответ стоит посчитать один раз и переиспользовать. Это и есть динамическое программирование. Достаточно один раз сосчитанную fib(i) где-то запомнить — и каждое значение посчитается ровно однажды.

Два способа переиспользовать ответ

Запомнить ответ можно двумя путями, и они дают два стиля DP.

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

def fib(n, memo)
  return memo[n] if memo.key?(n)
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
end
 
memo = { 0 => 0, 1 => 1 }
fib(10, memo) # => 55

Первый вызов fib(10, memo) спускается до fib(2), кладёт его в memo, и второй раз fib(2) уже не считается — memo.key? возвращает готовое значение.

Второй путь — отказаться от рекурсии и заполнять ответы в правильном порядке самому. fib(i) зависит от двух меньших значений, поэтому если идти от i = 2 вверх, к моменту расчёта fib(i) оба слагаемых уже лежат в массиве. Такой стиль идёт «снизу вверх», от базовых случаев к искомому, и называется bottom-up (табуляция — заполнение таблицы):

def fib(n)
  return n if n < 2
  dp = Array.new(n + 1)
  dp[0] = 0
  dp[1] = 1
  (2..n).each { |i| dp[i] = dp[i - 1] + dp[i - 2] }
  dp[n]
end

Результат тот же, но время меняется принципиально: каждое из n + 1 значений считается один раз, поэтому вместо экспоненты получаем O(n). А раз для очередного шага нужны только два предыдущих значения, весь массив можно и не хранить — достаточно двух переменных, и память падает до O(1).

Из чего состоит любой DP

Fibonacci показал общий скелет. В любой задаче, которую решает DP, есть три части:

Состояние (state) — компактное описание того, «где мы находимся» в задаче и что нужно знать, чтобы продолжить. У Фибоначчи состояние — это число i, ответ для него — fib(i).
Переход (recurrence) — как ответ для состояния выражается через ответы для более простых состояний. У Фибоначчи переход — fib(i) = fib(i - 1) + fib(i - 2).
Хранилище — где лежат уже посчитанные ответы, чтобы не считать дважды: массив (когда состояние — это индекс) или хеш-таблица (когда состояние — произвольный ключ).

Top-down и bottom-up — это лишь два способа обойти состояния: рекурсией с кэшем либо циклом в порядке зависимостей. Скелет одинаков.

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

время ≈ число состояний × число переходов на состояние.

У Фибоначчи это n состояний на один переход = O(n).

Считать DP умеет не только минимум или максимум. Тем же скелетом решают разные вопросы про состояние: минимальную или максимальную стоимость, количество способов что-то собрать, достижимость — можно ли вообще прийти в это состояние (ответ «да/нет» вместо числа). Меняется только то, что хранится в ячейке и как сливаются ответы в переходе.

Исторически слово programming здесь означает «математическое программирование» (оптимизацию), а не «написание кода».

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

Фибоначчи попал под DP не случайно. Чтобы приём дал ускорение, нужны два условия одновременно.

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

Оптимальная подструктура. Лучшее решение целиком можно собрать из лучших решений частей. У Фибоначчи это очевидно — сумма складывается из двух меньших. Но так не всегда: если оптимум целого нельзя получить, склеив оптимумы частей, переход даст неправильный ответ, и DP здесь не работает.

Когда состояние двумерно: путь по решётке

У Фибоначчи состояние — одно число. Покажем DP там, где состояние сложнее, на классической задаче о пути.

Есть прямоугольная таблица cost, в каждой клетке — стоимость. Из клетки (0, 0) можно ходить только вправо и вниз. Нужен путь до правого нижнего угла с наименьшей суммой стоимостей. Прямой перебор перебирает все пути, но их число растёт лавиной: на каждой клетке выбор из двух направлений, и для решётки n × m путей — порядка сочетаний из n + m шагов. DP напрашивается, потому что лучший путь до клетки (i, j) зависит только от лучших путей до двух соседей — сверху и слева.

Состояние: координаты клетки (i, j).
Ответ для состояния: dp[i][j] — минимальная стоимость пути до (i, j). Раз состояние — пара индексов, хранилище двумерное: таблица dp, где dp[i][j] адресуется двумя индексами, как клетка в cost.
Переход: в клетку (i, j) приходят либо сверху, либо слева, и выгоднее тот сосед, чей путь дешевле:

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

База: первая строка и первый столбец. Туда можно прийти единственным способом — всё время вправо или всё время вниз, — поэтому их суммы считаются напрямую, без выбора.

Заполнять dp нужно так, чтобы к расчёту (i, j) соседи сверху и слева уже были готовы. Это даёт порядок: строка за строкой, слева направо. Рекурсии тут нет, но DP это или нет — определяет не рекурсия, а наличие скелета: есть состояние (i, j), есть переход, и таблица хранит ответы для подзадач.

Прогоним на маленькой решётке:

Первая строка dp — нарастающие суммы только вправо (1, 1+3, 4+1), первый столбец — только вниз. Каждую внутреннюю клетку берём по переходу: dp[1][1] = 5 + min(4, 2) = 7. Ответ — dp[2][2] = 7: самый дешёвый путь идёт вправо, вправо, вниз, вниз (1 + 3 + 1 + 1 + 1).

Какой стиль выбрать

Top-down (мемоизация) обычно проще написать и отладить: рекурсия повторяет формулу перехода почти дословно, а кэш заполняется только теми состояниями, что реально встретились. Bottom-up даёт больше контроля над памятью и порядком вычислений: видно, какие состояния живут одновременно (у Фибоначчи — лишь два, отсюда сжатие до O(1)), а проход по таблице по соседним адресам ложится на локальность данных в кеше — соседние ячейки оказываются в одной кеш-линии, и обход идёт быстрее, чем прыжки рекурсии по разным адресам.

Как построить DP: чеклист

Скелет «состояние → переход → хранилище» превращается в рабочий порядок действий.

Состояние. Что нужно знать, чтобы продолжить решение? Часто это набор: индекс i, оставшаяся ёмкость, набор уже выбранных объектов.
Переход. Из каких более простых состояний собирается текущее и какой ценой?
База. Какие состояния известны сразу, без вычислений?
Оценка времени. Сколько всего состояний и сколько переходов на каждое? Их произведение и есть сложность — если она слишком велика, состояние выбрано слишком «богатым».
Порядок вычислений. Расположить расчёт так, чтобы к моменту обработки состояния все состояния, от которых оно зависит, уже были посчитаны.

Когда состояние — это набор: DP по подмножествам

Иногда «где мы находимся» — это набор уже выбранных объектов (например, таблицы, которые уже соединены в запросе). Набор из N объектов удобно кодировать одним целым числом: его двоичная запись — это битовая маска mask, где бит номер i стоит, если объект i уже в наборе. Тогда состояние — просто число, а хранилище — обычный массив dp, проиндексированный маской.

dp[mask] = лучшая стоимость собрать ровно этот набор
 
dp[mask] = минимум по объектам i внутри mask из:
    dp[mask без i] + цена_добавить(i, к набору mask без i)

Перебор всех 2^N подмножеств с N вариантами на каждое даёт O(2^N · N · cost_transition), где cost_transition — цена одного перехода. Это резко быстрее, чем перебирать все возможные порядки сборки (которых факториально много), но всё ещё экспоненциально по N — поэтому работает лишь при небольшом N, а дальше задачу решают приближённо, эвристиками (быстрыми правилами, дающими хороший, но не обязательно оптимальный ответ).

Так делает планировщик PostgreSQL при выборе порядка соединения: для небольшого числа таблиц он перебирает подмножества именно этим DP, а когда таблиц становится слишком много, переключается на эвристику.

Типичные ошибки

Слишком «богатое» состояние. Лишний параметр в состоянии умножает число состояний — и сложность вместе с ним. Перед кодом стоит прикинуть размер таблицы состояний (шаг 4 чеклиста).
Неверная база или порядок заполнения. Симптом — расчёт обращается к ячейке, которую ещё не успели посчитать, или ответы «плывут» на маленьких примерах. Лечится прогоном на решётке 3×3, как выше.
Путаница между «стоимостью» и «достижимостью». Один и тот же скелет считает то минимум, то количество способов, то ответ «да/нет». Это разные задачи: у них разное содержимое ячейки и разный переход, и их нельзя смешивать в одной таблице.

Sources

Bellman, R. Dynamic Programming (1957).
CLRS, 4th ed.: Dynamic Programming.
PostgreSQL Documentation (пример: v16): GEQO и join ordering. https://www.postgresql.org/docs/16/geqo.html

CS Notes

Explorer

dynamic-programming