Що таке табуляція (tabulation) у DP?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Табуляція (bottom-up) у динамічному програмуванні - це підхід, за якого ми ітеративно заповнюємо таблицю (масив/матрицю) значеннями підзадач, починаючи з базових випадків і рухаючись до відповіді. Рішення обчислюється без рекурсії, у заздалегідь обраному порядку, щоб кожна підзадача спиралася на вже пораховані менші. Це дає передбачувану складність O(кількість станів × кількість переходів) і дає змогу оптимізувати пам'ять (наприклад, до одного рядка/стовпця).

Детальний розбір

Ідея та відмінність від мемоізації (top-down)

Tabulation (bottom-up): будуємо відповідь знизу вгору. Немає рекурсії: задаємо порядок обходу станів, і кожен новий стан спирається на вже обчислені.
Memoization (top-down): використовуємо рекурсію з кешем. Стани обчислюються за запитом, глибина рекурсії може бути проблемою, але легше писати, коли переходи складні.
Коли відомий природний порядок обчислення і важливо уникати рекурсії/стека - табуляція є кращим вибором.

Ключові кроки табуляції

Визначте стан DP (що означає dp[i], dp[i][j] тощо).
Задайте структуру зберігання (масив/матриця) і розмір.
Ініціалізуйте базові випадки (граничні значення, нульові стани).
Визначте коректний порядок обходу, щоб потрібні підзадачі вже були пораховані.
Запишіть перехід (формулу), пройдіться по всіх станах і заповніть таблицю.
Зчитайте відповідь із потрібної комірки (зазвичай dp[n], dp[n][m]).

Приклад 1: Fibonacci - табуляція (O(n) за часом, O(1) за пам'яттю)

Стан: dp[i] - i-те число Фібоначчі; базові випадки: dp[0]=0, dp[1]=1; порядок: i від 2 до n.

function fib(n) {
  if (n <= 1) return n;
  let a = 0, b = 1; // зберігаємо лише два останніх значення
  for (let i = 2; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
}

console.log(fib(10)); // 55

Приклад 2: Кількість способів набрати суму (Coin Change, комбінації)

Задача: маючи необмежений набір монет coins, порахувати кількість способів набрати суму amount. Стан: dp[s] - кількість способів набрати суму s. База: dp[0]=1 (один спосіб набрати нуль - нічого не брати). Порядок: зовні - за монетами, всередині - за сумою у зростаючому порядку, щоб не рахувати перестановки як різні способи.

function countWays(coins, amount) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let s = coin; s <= amount; s++) {
      dp[s] += dp[s - coin];
    }
  }
  return dp[amount];
}

console.log(countWays([1, 2, 5], 5)); // 4 (1+1+1+1+1, 1+1+1+2, 1+2+2, 5)

Вибір порядку обходу: часті патерни

Необмежені предмети (unbounded, наприклад coin change «кількість способів»): зовнішній цикл за предметами, внутрішній - за «вагою/сумою» у зростаючому порядку.
Рюкзак 0/1 (кожен предмет не більше одного разу): зовнішній - за предметами, внутрішній - за вагою в спадному порядку, щоб не використовувати предмет повторно в тій самій ітерації.
Двовимірні DP (LCS, відстань редагування): заповнюємо матрицю за рядками/стовпцями, починаючи з базового рядка/стовпця.

Оптимізація пам'яті (rolling array)

Якщо перехід використовує лише попередній рядок/стовпець, можна зберігати тільки його. Приклад: рюкзак 0/1 з одним рядком і зворотним обходом ваги:

function knap01(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    const w = weights[i], v = values[i];
    for (let cap = W; cap >= w; cap--) {
      dp[cap] = Math.max(dp[cap], dp[cap - w] + v);
    }
  }
  return dp[W];
}

console.log(knap01([2,3,4], [4,5,10], 6)); // 14 (взяти предмети вагою 2 і 4)

Складність і коли застосовувати

Час: O(кількість станів × кількість переходів із кожного стану).
Пам'ять: O(кількість станів), часто зменшується до O(розміру одного шару) за акуратного порядку обходу.
Застосовувати, коли є DAG підзадач із природним порядком, важливо уникнути рекурсії, і/або потрібно обчислити не лише фінальну відповідь, а й усі проміжні значення.

Типові помилки в табуляції

Неправильна ініціалізація баз: dp[0] для «кількості способів» має дорівнювати 1, а не 0.
Помилковий порядок обходу, через який використовуються ще не пораховані значення або переобчислюються стани з повторним використанням елементів.
Зсуви індексів (off-by-one) у 1D/2D масивах.
Плутанина між мінімумами/максимумами і кількістю способів - різні бази й операції (+, min, max).

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.