Що таке стан (state) у DP?

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

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

Стан (state) у динамічному програмуванні - це мінімальний і достатній набір параметрів, який однозначно описує підзадачу так, щоб її розв'язок можна було повторно використати. Кількість усіх можливих станів визначає пам'ять і значною мірою час розв'язання.

Детальна відповідь

Що таке стан (state) у ДП

Стан у ДП - це формальний опис підзадачі через набір індексів/прапорів/значень, за якими ми:

зберігаємо результат (наприклад, мінімум, максимум, кількість способів, булеве можна/не можна);
однозначно розрізняємо підзадачі (жодні дві різні підзадачі не повинні мати однаковий стан);
можемо виразити переходи до простіших станів (оптимальна структура).

Типовий вигляд: dp[параметри] = шукана величина для підзадачі, описаної цими параметрами.

Як обрати коректний стан

Визначте, що саме ви хочете зберігати в dp (мінімум/максимум/лічильник/булеве/найкращий прибуток тощо).
Виділіть параметри, які розрізняють підзадачі: позиція/індекс, довжина префікса/суфікса, поточна місткість/сума, залишок за модулем, прапори (взяли/не взяли), маска відвіданих, остання обрана сутність тощо.
Перевірте оптимальну структуру: значення dp має виражатися через значення в «менших» станах.
Оцініть розмірність: кількість станів має бути прийнятною за пам'яттю і часом.
Сформулюйте переходи і порядок обчислення (top-down з мемоізацією або bottom-up/табуляція).
Задайте базові випадки (межі, порожні множини, нульові довжини).

Чим стан відрізняється від переходів і відповіді

Стан - «координати» підзадачі (яка саме це підзадача).
Переходи - як отримати стан з інших (рекурентна формула).
Відповідь - конкретний стан, що відповідає вихідній задачі (наприклад, dp[n], dp[n][m], dp[mask_all][last]).

Приклади станів і коду

1) Фібоначчі: dp[n] - n-те число

Стан: n. Зберігаємо: значення F(n). Перехід: F(n)=F(n-1)+F(n-2). База: F(0)=0, F(1)=1.

// Top-down (мемоізація)
const fibMemo = (function () {
  const memo = new Map();
  memo.set(0, 0);
  memo.set(1, 1);
  function f(n) {
    if (memo.has(n)) return memo.get(n);
    const val = f(n - 1) + f(n - 2);
    memo.set(n, val);
    return val;
  }
  return f;
})();

// Bottom-up (табуляція)
function fib(n) {
  if (n <= 1) return n;
  let a = 0, b = 1; // dp[n-2], dp[n-1]
  for (let i = 2; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
}

2) Кількість шляхів у сітці з перешкодами: dp[i][j]

Стан: клітинка (i, j). Зберігаємо: кількість шляхів до (i, j). Перехід: dp[i][j]=dp[i-1][j]+dp[i][j-1], якщо немає перешкоди. База: dp[0][0]=1, якщо старт без перешкоди.

function uniquePathsWithObstacles(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => Array(n).fill(0));
  if (grid[0][0] === 1) return 0;
  dp[0][0] = 1;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) { dp[i][j] = 0; continue; }
      if (i === 0 && j === 0) continue;
      const fromTop = i > 0 ? dp[i - 1][j] : 0;
      const fromLeft = j > 0 ? dp[i][j - 1] : 0;
      dp[i][j] = fromTop + fromLeft;
    }
  }
  return dp[m - 1][n - 1];
}

3) Рюкзак 0/1: dp[i][w]

Стан: (i, w) - розглядаємо перші i предметів при доступній місткості w. Зберігаємо: максимальну цінність. Перехід: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) при w ≥ weight[i]. База: dp[0][*]=0.

function knapSack(capacity, weights, values) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w]; // не беремо i-й
      if (w >= weights[i - 1]) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      }
    }
  }
  return dp[n][capacity];
}

// Оптимізація пам'яті (ковзний масив)
function knapSack1D(capacity, weights, values) {
  const n = weights.length;
  const dp = Array(capacity + 1).fill(0);
  for (let i = 0; i < n; i++) {
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

4) DP за підмножинами (приклад TSP): dp[mask][i]

Стан: (mask, i) - ми відвідали набір вершин mask, перебуваємо в i. Зберігаємо: мінімальну вартість шляху. Перехід: dp[mask][i] = min_j dp[mask \ {i}][j] + cost[j][i]. База: dp[1<<start][start] = 0. Тут важлива компресія стану через бітову маску.

function tsp(cost) {
  const n = cost.length;
  const N = 1 << n;
  const INF = 1e15;
  const start = 0;
  const dp = Array.from({ length: N }, () => Array(n).fill(INF));
  dp[1 << start][start] = 0;
  for (let mask = 0; mask < N; mask++) {
    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) === 0) continue;
      const cur = dp[mask][i];
      if (cur >= INF) continue;
      for (let j = 0; j < n; j++) {
        if (mask & (1 << j)) continue;
        const nextMask = mask | (1 << j);
        dp[nextMask][j] = Math.min(dp[nextMask][j], cur + cost[i][j]);
      }
    }
  }
  let ans = INF;
  for (let i = 0; i < n; i++) {
    ans = Math.min(ans, dp[N - 1][i] + cost[i][start]);
  }
  return ans;
}

Оцінка складності через стан

Час ≈ (кількість станів) × (середня кількість переходів на стан). Пам'ять ≈ кількість станів (з урахуванням оптимізацій, наприклад, ковзних масивів або компресії масками).

Фібоначчі: O(n) станів, O(1) переходів -> O(n) часу, O(1)/O(n) пам'яті.
Рюкзак: O(n·W) станів, O(1) переходів -> O(n·W) часу, O(n·W) або O(W) пам'яті.
TSP за масками: O(n·2^n) станів, O(n) переходів -> O(n^2·2^n) часу, O(n·2^n) пам'яті.

Типові помилки під час визначення стану

Недостатній стан: не включили параметр, від якого залежить відповідь (виникають неправильні повторні використання).
Надлишковий стан: додали зайвий параметр -> вибух розмірності та ресурсів.
Неправильний порядок обходу в bottom-up: використовуються ще не пораховані стани.
Погана ініціалізація: забуті базові випадки, неправильні типові значення (наприклад, -∞/∞ замість 0).
Дублювання підзадач: неправильне кодування стану (наприклад, невпорядковані пари без нормалізації).

Короткий чек-лист по state у ДП

Що зберігаю в dp? (мінімум/максимум/лічильник/булеве/найкраще)
Які параметри однозначно описують підзадачу? (індекси, прапори, маски...)
Чи є оптимальна структура і коректні переходи?
Чи прийнятна розмірність за часом/пам'яттю? (чи можлива компресія)
Чи обрано правильну ініціалізацію і порядок обчислення?

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

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

Premium

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