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

Динамическое программирование (dynamic programming, DP) — метод решения задач, разбивающий их на перекрывающиеся подзадачи и сохраняющий результаты для избежания повторных вычислений.

Зачем нужно

Многие задачи имеют экспоненциальную сложность при наивном переборе. DP снижает её до полиномиальной, запоминая результаты подзадач. Fibonacci без DP: O(2^n). С DP: O(n). Это фундаментальная техника для задач оптимизации, счёта и поиска, встречающаяся на всех технических собеседованиях.

Где используется

  • Оптимизация маршрутов и расписаний
  • Выравнивание последовательностей ДНК (биоинформатика)
  • Сжатие данных (алгоритм Хаффмана содержит DP-элементы)
  • Компиляторы: парсинг с CYK-алгоритмом
  • Игры: оценка позиций в шахматах (minimax + memoization)

Основной контент

Два признака применимости DP

  1. Overlapping subproblems (перекрывающиеся подзадачи): одни и те же подзадачи решаются многократно.
  2. Optimal substructure (оптимальная подструктура): оптимальное решение задачи строится из оптимальных решений подзадач.

Два подхода: мемоизация vs табуляция

Top-down с мемоизацией

// Fibonacci — O(n) время, O(n) память
function fib(n, memo = new Map) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, result);
  return result;
}

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

// Fibonacci — O(n) время, O(1) память (оптимизировано)
function fibDP(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

Классическая задача: Longest Common Subsequence (LCS)

// LCS двух строк — O(m*n)
function lcs(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;      // символы совпали
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // пропустить один
      }
    }
  }
  return dp[m][n];
}

lcs("ABCBDAB", "BDCAB"); // 4 ("BCAB" или "BDAB")

Классическая задача: Coin Change

// Минимальное число монет для суммы amount
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a && dp[a - coin] + 1 < dp[a]) {
        dp[a] = dp[a - coin] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

coinChange([1, 5, 6, 9], 11); // 2 (5+6)

Шаблон решения DP-задачи

1. Определить состояние: dp[i] означает ___
2. Написать рекуррентное соотношение
3. Определить базовые случаи
4. Определить порядок вычислений (снизу вверх)
5. Оптимизировать память (часто можно с O(n²) до O(n))

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

  • Не определить рекуррентное соотношение явно — код получается запутанным и трудно отлаживаемым.
  • Забывать базовые случаи (dp[0], dp[1]) — приводит к неверным результатам или ошибкам.
  • Неправильный порядок вычислений в bottom-up: dp[i] зависит от dp[i-1], значит считать нужно слева направо.
  • Использовать мемоизацию там, где лучше табуляция — рекурсия с большой глубиной может вызвать stack overflow.

Связанные темы

Ресурсы