Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке стан (state) у DP?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Стан (state)** у динамічному програмуванні - це мінімальний і достатній набір параметрів, який однозначно описує підзадачу так, щоб її розв'язок можна було повторно використати. Кількість усіх можливих станів визначає пам'ять і значною мірою час розв'язання. **Ключове:** час роботи приблизно дорівнює (кількість станів) × (середня кількість переходів на стан).Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь **Стан (state)** у динамічному програмуванні - це мінімальний і достатній набір параметрів, який однозначно описує підзадачу так, щоб її розв'язок можна було повторно використати. Кількість усіх можливих станів визначає пам'ять і значною мірою час розв'язання. ## Детальна відповідь ## Що таке стан (state) у ДП Стан у ДП - це формальний опис підзадачі через набір індексів/прапорів/значень, за якими ми: - зберігаємо результат (наприклад, мінімум, максимум, кількість способів, булеве можна/не можна); - однозначно розрізняємо підзадачі (жодні дві різні підзадачі не повинні мати однаковий стан); - можемо виразити переходи до простіших станів (оптимальна структура). Типовий вигляд: dp[параметри] = шукана величина для підзадачі, описаної цими параметрами. ## Як обрати коректний стан 1. Визначте, що саме ви хочете зберігати в dp (мінімум/максимум/лічильник/булеве/найкращий прибуток тощо). 2. Виділіть параметри, які розрізняють підзадачі: позиція/індекс, довжина префікса/суфікса, поточна місткість/сума, залишок за модулем, прапори (взяли/не взяли), маска відвіданих, остання обрана сутність тощо. 3. Перевірте оптимальну структуру: значення dp має виражатися через значення в «менших» станах. 4. Оцініть розмірність: кількість станів має бути прийнятною за пам'яттю і часом. 5. Сформулюйте переходи і порядок обчислення (top-down з мемоізацією або bottom-up/табуляція). 6. Задайте базові випадки (межі, порожні множини, нульові довжини). ## Чим стан відрізняється від переходів і відповіді - Стан - «координати» підзадачі (яка саме це підзадача). - Переходи - як отримати стан з інших (рекурентна формула). - Відповідь - конкретний стан, що відповідає вихідній задачі (наприклад, 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? (мінімум/максимум/лічильник/булеве/найкраще) - Які параметри однозначно описують підзадачу? (індекси, прапори, маски...) - Чи є оптимальна структура і коректні переходи? - Чи прийнятна розмірність за часом/пам'яттю? (чи можлива компресія) - Чи обрано правильну ініціалізацію і порядок обчислення?Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.