Dynamic Programming

Dynamic Programming — это искусство превращать экспоненциальную сложность в полиномиальную через запоминание уже решённых подзадач. Если Divide & Conquer разбивает задачу на независимые части, то DP работает с пересекающимися подзадачами: одна и та же подзадача встречается многократно, и вместо повторного вычисления мы сохраняем результат. Это и есть две золотые характеристики DP: overlapping subproblems и optimal substructure (решение строится из оптимальных решений подзадач).

Представьте классику — числа Фибоначчи. Наивная рекурсия fib(n) = fib(n-1) + fib(n-2) пересчитывает fib(5) десятки раз для fib(10) — это O(2ⁿ) катастрофа. Добавим мемоизацию — храним результаты в массиве, проверяем перед вычислением. Теперь каждое fib(k) вычисляется один раз → O(n) время, O(n) память. Ещё лучше: заметим, что нужны только два предыдущих значения, итерируем снизу вверх с двумя переменными → O(n) время, O(1) память. Это и есть bottom-up DP с оптимизацией памяти.

Когда применять

Сигналы того, что задача — DP:

• Формулировка типа «количество способов», «минимальная/максимальная стоимость», «можно ли достичь».
• Небольшие ограничения: n ≤ 1000 для O(n²), n ≤ 100 для O(n³).
• Видна рекурсивная структура с пересекающимися подзадачами.
• Greedy провалился — нашли контрпример.

Проверь два условия: (1) оптимальная подструктура — можно ли решение составить из решений подзадач? (2) пересекающиеся подзадачи — вычисляется ли одна подзадача многократно? Если да — DP подходит.

Идея

Два подхода к DP:

• Top-down (рекурсия с мемоизацией) — пишется интуитивнее, код похож на рекурсивное определение, легче отлаживать. Минус: накладные на стек вызовов, риск StackOverflow на глубокой рекурсии.
• Bottom-up (заполнение таблицы итеративно) — нет накладных на рекурсию, проще оптимизировать память (rolling array, когда dp[i] зависит только от dp[i-1]). Минус: требует понимания порядка обхода.

На собеседовании рекомендую начинать с top-down для ясности, потом, если попросят оптимизировать — переводить в bottom-up.

Три кита DP:

1. Определить состояние — что минимально достаточно знать, чтобы описать подзадачу?
2. Написать переход — как dp[state] выражается через предыдущие состояния?
3. Базовые случаи — с чего начинаем?

Пример: LCS (Longest Common Subsequence). Состояние: dp[i][j] = длина LCS для префиксов a[0..i-1] и b[0..j-1]. Переход: если a[i-1] === b[j-1], dp[i][j] = dp[i-1][j-1] + 1; иначе dp[i][j] = max(dp[i-1][j], dp[i][j-1]). База: dp[0][*] = 0, dp[*][0] = 0. Ответ: dp[n][m].

Реализация: Longest Increasing Subsequence

Задача: дан массив целых чисел nums. Найти длину наибольшей возрастающей подпоследовательности (необязательно подряд). Пример: [10,9,2,5,3,7,101,18] → LIS длины 4.

Подход 1: DP O(n²)

Состояние dp[i] = длина LIS, заканчивающейся на nums[i]. Переход: для каждого j < i, если nums[j] < nums[i], то dp[i] = max(dp[i], dp[j] + 1). База: dp[i] = 1 для всех. Ответ: max(dp[...]).

function lengthOfLIS_DP(nums: number[]): number {
  if (!nums.length) return 0;

  const dp = Array(nums.length).fill(1);
  let maxLen = 1;

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxLen = Math.max(maxLen, dp[i]);
  }

  return maxLen;
}

Подход 2: Patience Sorting O(n log n)

Поддерживаем массив tails, где tails[i] — минимальный концевой элемент возрастающей подпоследовательности длины i+1. Для каждого num находим бинарным поиском первый элемент ≥ num и заменяем его. Если num больше всех — добавляем в конец. Длина tails в конце — ответ.

function lengthOfLIS_Binary(nums: number[]): number {
  if (!nums.length) return 0;

  const tails: number[] = [];

  for (const num of nums) {
    let left = 0;
    let right = tails.length;

    // Бинарный поиск: первый элемент >= num
    while (left < right) {
      const mid = left + ((right - left) >> 1);
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }

    if (left === tails.length) tails.push(num);
    else tails[left] = num;
  }

  return tails.length;
}

Трассировка Patience Sorting

Для [10,9,2,5,3,7,101,18]:

num=10:  tails=[]      → push   → [10]
num=9:   позиция 0 (≥9) → replace → [9]
num=2:   позиция 0     → replace → [2]
num=5:   позиция 1 (end) → push  → [2,5]
num=3:   позиция 1     → replace → [2,3]
num=7:   позиция 2 (end) → push  → [2,3,7]
num=101: позиция 3 (end) → push  → [2,3,7,101]
num=18:  позиция 3     → replace → [2,3,7,18]
Длина 4 → ответ 4

Интуиция: tails[i] — наименьший конец последовательности длины i+1. Заменяя большие элементы меньшими на той же позиции, мы не меняем длину, но улучшаем возможности для будущих элементов.

Пример 2: Coin Change (Unbounded Knapsack)

Даны монеты coins и сумма amount. Найти минимальное количество монет, составляющих amount (монеты можно использовать многократно). Если невозможно — вернуть -1.

function coinChange(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0; // базовый случай: 0 монет для суммы 0

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1, 2, 5], 11)); // 3
console.log(coinChange([2], 3));         // -1

Пример 3: Edit Distance (Levenshtein)

Даны строки word1 и word2. Найти минимальное число операций (insert, delete, replace) для превращения word1 в word2.

function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) dp[i][0] = i; // удалить все
  for (let j = 0; j <= n; j++) dp[0][j] = j; // вставить все

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete
          dp[i][j - 1],     // insert
          dp[i - 1][j - 1], // replace
        );
      }
    }
  }

  return dp[m][n];
}

:::tip Оптимизация памяти dp[i][j] зависит только от dp[i-1][*] и dp[i][j-1]. Можем хранить две строки (prev, curr) вместо всей таблицы → память O(min(m, n)). :::

Сложность

• LIS DP O(n²): время O(n²), память O(n).
• LIS patience sort: время O(n log n), память O(n) — оптимально для больших n.
• Coin Change: время O(n · amount), память O(amount).
• Edit Distance: время O(n · m), память O(n · m), оптимизируется до O(min(n, m)).

Дополнительные паттерны

DP на интервалах. Состояние dp[l][r] — ответ для подотрезка [l, r]. Обход по возрастанию длины. Примеры: Matrix Chain Multiplication, Burst Balloons, Longest Palindromic Subsequence. Сложность O(n³).

DP на деревьях. Post-order обход: решаем дочерние состояния перед родителем. Примеры: Tree Diameter, House Robber III, Binary Tree Cameras. Состояние часто dp[node][flag], где flag — дополнительная информация (взят узел или нет).

Bitmask DP. Для n ≤ 20–25. Состояние включает битовую маску посещённых элементов. Пример: TSP — dp[mask][i] = минимальная стоимость посетить вершины mask, закончив в i. Сложность O(2ⁿ · n²).

Digit DP. Подсчёт чисел ≤ N с определённым свойством (например, сумма цифр кратна 3). Состояние: (pos, tight, leadingZero, ...). Advanced техника, но на топовых собесах (Google L5+, Meta E5+) встречается.

Типичные ошибки и подводные камни

• Неправильное состояние — забыли учесть важную информацию или состояние слишком грубое/детальное.
• Неправильный порядок обхода — обращаетесь к dp[...], который ещё не вычислен.
• Забыли базовый случай — всё превращается в 0 или Infinity.
• Off-by-one в индексах: dp[i] обычно соответствует i-му префиксу, но элемент массива — nums[i-1].
• Переполнение int для больших сумм — в JS используйте BigInt при необходимости.
• TLE на n = 10⁵: O(n²) обычно проходит для n = 10⁴, но не для 10⁵.

Follow-up вопросы

• В чём разница между top-down и bottom-up DP? Top-down: рекурсия с мемоизацией. Плюсы — интуитивен, вычисляет только нужные состояния. Минусы — стек, может переполниться. Bottom-up: итеративное заполнение от базовых случаев. Плюсы — нет рекурсии, легче оптимизировать память. Минусы — нужно понять порядок обхода.

• Как восстановить решение, а не только его значение? Сохраняйте указатель «откуда пришёл оптимум». Например, в Edit Distance запомните, какая операция была. После заполнения таблицы идите обратно от dp[m][n], следуя по сохранённым указателям.

• Как оптимизировать память для 2D DP? Если dp[i][j] зависит только от dp[i-1][*] и dp[i][j-1], храните две строки prev и curr и swap-айте после строки i. Пример: LCS — O(n·m) → O(min(n, m)).

• Почему для 0/1 Knapsack внутренний цикл по весу идёт справа налево? Чтобы не использовать предмет многократно. Если идти слева направо, dp[w] обновится, и при w' > w мы используем уже обновлённый dp[w], т.е. предмет взят дважды. Справа налево гарантирует однократное использование. Для unbounded knapsack идём слева направо.

• Найти количество путей в сетке m×n с препятствиями? dp[i][j] = количество путей до клетки (i, j). База: dp[0][0] = 1 (если нет препятствия), иначе 0. Переход: dp[i][j] = dp[i-1][j] + dp[i][j-1], если нет препятствия; иначе 0. Время O(m·n), память сжимается до O(n).

Чеклист на собес

• Сформулируй состояние одной фразой: «dp[…] = …».
• Запиши переход и базу.
• Проверь порядок обхода — все нужные значения уже вычислены?
• Считай сложность по формуле: число состояний × время на переход.
• После top-down предложи bottom-up + оптимизацию памяти.
• Покажи, как восстановить ответ (если просят).