Мемоизация vs табуляция

Мемоизация (memoization) — top-down подход к DP с кэшированием результатов рекурсивных вызовов; табуляция (tabulation) — bottom-up подход, заполняющий таблицу DP итеративно от базовых случаев.

Зачем нужно

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

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

  • Мемоизация: любые рекурсивные задачи с перекрывающимися подзадачами
  • Табуляция: DP-задачи с фиксированным порядком вычислений
  • Оба подхода: Fibonacci, Knapsack, LCS, Coin Change, Longest Increasing Subsequence

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

Мемоизация (Top-down)

Начинаем с оригинальной рекурсии, добавляем кэш. Вычисляем только нужные подзадачи.

// Fibonacci с мемоизацией
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;
}
// fib(40) = ~102 миллисекунды → ~0.01мс

// Coin Change с мемоизацией
function coinChange(coins, amount, memo = new Map) {
  if (amount === 0) return 0;
  if (amount < 0) return Infinity;
  if (memo.has(amount)) return memo.get(amount);

  let min = Infinity;
  for (const coin of coins) {
    const sub = coinChange(coins, amount - coin, memo);
    min = Math.min(min, sub + 1);
  }
  memo.set(amount, min);
  return min;
}

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

Начинаем с базовых случаев, итеративно строим таблицу.

// Fibonacci с табуляцией
function fibTab(n) {
  if (n <= 1) return n;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 0; dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

// Оптимизация памяти до O(1)
function fibOpt(n) {
  if (n <= 1) return n;
  let [prev, curr] = [0, 1];
  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
}

// Coin Change с табуляцией
function coinChangeTab(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] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Сравнение подходов

Аспект Мемоизация (top-down) Табуляция (bottom-up)
Реализация Проще (рекурсия + кэш) Сложнее (явный порядок)
Вычисление Только нужные подзадачи Все подзадачи
Память O(n) стек + кэш O(n) таблица, нет стека
Stack overflow При большом n Нет риска
Оптимизация памяти Труднее Легко (rolling array)
Когда выбрать Не все подзадачи нужны Нужны все подзадачи

Оптимизация памяти в табуляции (rolling array)

// LCS: вместо матрицы m×n хранить только 2 строки
function lcsOpt(s1, s2) {
  const m = s1.length, n = s2.length;
  let prev = new Array(n + 1).fill(0);
  let curr = new Array(n + 1).fill(0);
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      curr[j] = s1[i-1] === s2[j-1]
        ? prev[j-1] + 1
        : Math.max(prev[j], curr[j-1]);
    }
    [prev, curr] = [curr, prev];
  }
  return prev[n]; // O(n) вместо O(m*n) памяти
}

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

  • Мемоизация без явного кэша — использование глобальной переменной ломается при нескольких вызовах функции.
  • Табуляция с неправильным порядком заполнения: dp[i] зависит от dp[i-1], значит нужно идти слева направо, а не в обратном направлении.
  • Перепутать ключ кэша: при нескольких параметрах нужен составной ключ ${n},${k}, а не просто n.
  • Применять мемоизацию к задачам без перекрывающихся подзадач — тогда кэш никогда не даёт попаданий.

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

Ресурсы