CS Notes

dynamic-programming

6 min read

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

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

Sources

Иногда задача выглядит так, будто вариантов слишком много: «переберём все варианты и выберем лучший» работает, но время растёт экспоненциально. Динамическое программирование (DP) сокращает работу за счёт простой идеи: если одна и та же подзадача встречается много раз, её решение стоит посчитать один раз и переиспользовать.

Что такое DP

DP в практическом смысле — это «таблица ответов на подзадачи»:

  1. Мы выбираем состояние (state) — компактное описание того, «где мы находимся» в задаче.
  2. Мы пишем переход (recurrence) — как ответ для состояния выражается через ответы для более простых состояний.
  3. Мы сохраняем уже посчитанные значения (в массиве или хеш‑таблице), чтобы не пересчитывать одно и то же.

DP применяют не только для «минимума/максимума». Типичные формулировки:

  • минимальная/максимальная стоимость (min/max),
  • количество способов (count),
  • возможность/достижимость (boolean).

Практическая оценка времени почти всегда сводится к одному правилу:
время ≈ число состояний × число переходов на состояние.

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

DP, memoization и рекурсия — что чем является

DP — это метод решения (state + переход + сохранение результатов). Дальше остаётся выбор, как именно это реализовать:

  • Top-down DP (memoization): пишем рекурсивную функцию и кэшируем результаты f(state). Рекурсия здесь — удобный способ «дойти» до базовых случаев.
  • Bottom-up DP (табуляция): заполняем таблицу в циклах в порядке зависимостей и не используем рекурсию в коде вообще.

Memoization — частый инструмент DP, но не синоним. Если у задачи нет перекрывающихся подзадач, кэш может почти ничего не дать — тогда это будет «кэш на всякий случай», а не DP как способ ускорения.

Пример 1: Fibonacci (перекрывающиеся подзадачи)

Рекурсивное определение:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

Наивная рекурсия пересчитывает одно и то же много раз:

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  └─ fib(1)
│  └─ fib(2)   ← повтор
└─ fib(3)      ← повтор

DP убирает повторения: каждая fib(i) вычисляется один раз и кладётся в кэш.

Top-down (memoization):

Как проверить пример: открой irb, вставь код и вызови fib(10, 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

Bottom-up (табуляция):

Как проверить пример: в том же irb вставь функцию и вызови fib(10).

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

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

Пример 2: минимальная стоимость пути по решётке (bottom-up без рекурсии)

Задача: есть таблица cost[i][j]. Из клетки (0,0) можно ходить только вправо и вниз. Нужно найти минимальную сумму cost на пути до (n-1, m-1).

Наивный перебор пытается рассмотреть все возможные пути, а их количество растёт комбинаторно. DP здесь появляется естественно, потому что «лучший путь до клетки (i,j)» зависит только от лучших путей до соседей сверху и слева.

Состояние: координаты клетки (i, j)
Ответ для состояния: dp[i][j] — минимальная стоимость пути до (i, j)
Переход:

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

База: первая строка и первый столбец (туда можно прийти только одним способом: всё время вправо или всё время вниз).

На практике это заполняется двумя вложенными циклами по i и j. Здесь нет рекурсии, но это всё равно DP: есть state, есть переход, и таблица dp хранит ответы для подзадач.

Мини‑пример:

cost:
  1  3  1
  1  5  1
  4  2  1
 
dp:
  1  4  5
  2  7  6
  6  8  7

Ответ — dp[2][2] = 7: самый дешёвый путь идёт вправо, вправо, вниз, вниз (1 + 3 + 1 + 1 + 1).

Когда DP подходит

DP обычно уместно, когда одновременно выполняются два условия:

  1. Перекрывающиеся подзадачи. При наивном переборе ты снова и снова приходишь к одним и тем же промежуточным состояниям.
  2. Оптимальная подструктура. Лучшее решение целиком можно собрать из лучших решений частей (с корректной «стыковкой» на границе).

Если подзадачи почти не повторяются, memoization мало поможет. Если «лучшее целиком» не складывается из «лучших частей», DP даст неправильный ответ.

Два стиля: memoization и bottom-up

Top-down (memoization): пишем рекурсивное решение и кэшируем результаты для состояний, которые реально встретились.

Bottom-up: перечисляем все нужные состояния в правильном порядке и заполняем таблицу явно.

Обычно top-down проще написать и отладить, а bottom-up проще контролировать по памяти и порядку вычислений (особенно если важна локальность данных в кеше CPU).

Как построить DP (практический чеклист)

  1. Определи состояние. Что должно быть известно, чтобы продолжать решение? (индекс i, оставшаяся ёмкость w, подмножество mask…)
  2. Определи переход. Из каких предыдущих состояний получается текущее и сколько это стоит?
  3. Определи базу. Какие состояния очевидны без вычислений?
  4. Проверь размерность. Сколько состояний получится и сколько переходов на каждое? Это и есть твоя асимптотика.
  5. Выбери порядок вычислений. Чтобы при расчёте состояния все нужные «предки» уже были посчитаны.

DP по подмножествам (bitmask DP)

Когда в задаче есть «набор уже выбранных объектов» (например, таблицы, которые уже соединены), удобное состояние — битовая маска mask, где бит i означает «объект i уже внутри».

Типичная форма:

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

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

Пример реального применения: оптимизация порядка JOIN в PostgreSQL использует перебор подмножеств для небольшого числа таблиц, а дальше переключается на эвристический режим (см. порядок соединения).

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

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

Sources

Graph View

Backlinks