Паттерн: Динамическое программирование

Признак в условии

• «сколькими способами», «максимум / минимум при выборе»
• решение для n выражается через решения для меньших входов
• наивная рекурсия пересчитывает одно и то же (экспонента)

Порядок действий

1. Что такое состояние? dp[i] - ответ для префикса длины i / для суммы i.
2. Рекуррента: как dp[i] выражается через предыдущие.
3. База: dp[0] и краевые значения.
4. Порядок обхода: снизу вверх или мемоизация сверху вниз.
5. Свернуть память: если нужны только dp[i−1] и dp[i−2] - хватит двух переменных.

Шаблон

const dp = new Array(n + 1).fill(Infinity);   // недостижимое, а не 0
dp[0] = 0;
for (let i = 1; i <= n; i++) {
  for (const step of варианты) {
    if (step <= i) dp[i] = Math.min(dp[i], dp[i - step] + 1);
  }
}

let prev = 1, cur = 1;                        // свёрнутая память
for (let i = 2; i <= n; i++) [prev, cur] = [cur, prev + cur];

Сложность

Обычно O(состояний × переходов), память O(состояний) или O(1) после свёртки.

Частые ошибки

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

Мнемоника

«Состояние, переход, база, свёртка»

Не путать с

• Жадность - жадность работает, когда локально лучший выбор всегда часть глобального ответа. Есть контрпример - только динамика
• Перебор с возвратом - динамика - это перебор, у которого подзадачи повторяются; признак - «сколькими способами» и «максимум/минимум при ограничении»

Задачи на этот паттерн

• числа Фибоначчи с мемоизацией
• варианты подъёма по лестнице
• максимальная сумма подмассива
• минимум монет
• нельзя брать соседние
• наибольшая общая подпоследовательность
• число путей в сетке
• разбиение на слова
• число расшифровок
• минимальная сумма пути в сетке
• расстояние редактирования

Суть

Динамика это «перебор с памятью». Если ответ складывается из ответов на подзадачи, и подзадачи повторяются, решаем каждую один раз и запоминаем. Экспонента превращается в полином.

Как распознать по условию

• «сколько способов», «минимальная / максимальная стоимость», «можно ли»;
• выбор на каждом шаге влияет на будущее (взять или не взять, куда шагнуть);
• жадность ломается на маленьком контрпримере;
• «подпоследовательность» (не непрерывная), «расстояние редактирования», «рюкзак»;
• ограничения n до 10³-10⁴ для O(n²) или произведение размеров до 10⁷.

Пять шагов

1. Состояние: что значит dp[i]. Скажи вслух одним предложением.
2. Переход: как dp[i] выражается через меньшие.
3. База: dp[0], пустая строка, первая клетка.
4. Порядок: так, чтобы зависимости были посчитаны раньше.
5. Ответ: dp[n] или максимум по таблице.

Сверху вниз: рекурсия + мемо

function climb(n, memo = new Map()) {
  if (n <= 1) return 1;
  if (memo.has(n)) return memo.get(n);
  const r = climb(n - 1, memo) + climb(n - 2, memo);
  memo.set(n, r);
  return r;
}

Проще придумать, но тратит стек и может переполнить его на больших n.

Снизу вверх: таблица

function coinChange(coins, S) {
  const dp = new Array(S + 1).fill(Infinity);
  dp[0] = 0;
  for (let s = 1; s <= S; s++) {
    for (const c of coins) {
      if (c <= s) dp[s] = Math.min(dp[s], dp[s - c] + 1);
    }
  }
  return dp[S] === Infinity ? -1 : dp[S];
}

Двумерная динамика

Две строки или сетка → dp[i][j]. Наибольшая общая подпоследовательность:

// dp[i][j] = LCS для a[0..i) и b[0..j)
dp[i][j] = a[i-1] === b[j-1]
  ? dp[i-1][j-1] + 1
  : Math.max(dp[i-1][j], dp[i][j-1]);

Сложность O(n · m). Если переход смотрит только на предыдущую строку, память сжимается до O(m).

Сложность

Число состояний × работа на переход. Лестница: n × O(1). Монеты: S × k. LCS: n · m × O(1).

Ловушки

• Нечёткое определение состояния: потом не сходится переход.
• Инициализация нулями в задачах на минимум.
• Рюкзак 0/1 в одном массиве с прямым порядком цикла (предмет берётся дважды).
• Число способов размена: порядок циклов решает, считаем ли перестановки.
• new Array(n).fill([]) создаёт одну общую строку: нужен Array.from({ length: n }, () => []).

Что спросят на собесе

• Чем DP отличается от жадности и от рекурсии?
• Мемоизация или таблица: плюсы и минусы.
• Реши размен монет и объясни сложность.
• Как сэкономить память в двумерной динамике?