Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що таке табуляція (tabulation) у DP?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

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

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

1. Визначте стан DP (що означає dp[i], dp[i][j] тощо).
2. Задайте структуру зберігання (масив/матриця) і розмір.
3. Ініціалізуйте базові випадки (граничні значення, нульові стани).
4. Визначте коректний порядок обходу, щоб потрібні підзадачі вже були пораховані.
5. Запишіть перехід (формулу), пройдіться по всіх станах і заповніть таблицю.
6. Зчитайте відповідь із потрібної комірки (зазвичай 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).

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати652 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.