{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Короткий ответ" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Состояние (state) в динамическом программировании — это минимальный и достаточный набор параметров, который однозначно описывает подзадачу так, чтобы её решение можно было переиспользовать. Число всех возможных состояний определяет память и во многом время решения." } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Подробный ответ" }] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Что такое состояние (state) в ДП" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Состояние в ДП — это формальное описание подзадачи через набор индексов/флагов/значений, по которым мы:" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "храним результат (например, минимум, максимум, количество способов, булево можно/нельзя);" }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "однозначно различаем подзадачи (никакие две разные подзадачи не должны иметь одно и то же состояние);" }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "можем выразить переходы к более простым состояниям (оптимальная структура)." }] } ] } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Типичный вид: dp[параметры] = искомая величина для подзадачи, описанной этими параметрами." } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Как выбрать корректное состояние" }] }, { "type": "orderedList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Определите, что именно вы хотите хранить в dp (минимум/максимум/счёт/булево/лучший профит и т. п.)." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Выделите параметры, которые различают подзадачи: позиция/индекс, длина префикса/суффикса, текущая вместимость/сумма, остаток по модулю, флаги (взяли/не взяли), маска посещённых, последняя выбранная сущность и т. д." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Проверьте оптимальную структуру: значение dp должно выражаться через значения в «меньших» состояниях." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Оцените размерность: число состояний должно быть приемлемым по памяти и времени." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Сформулируйте переходы и порядок вычисления (top-down с мемоизацией или bottom-up/табуляция)." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Задайте базовые случаи (границы, пустые множества, нулевые длины)." }] } ] } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Чем состояние отличается от переходов и ответа" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Состояние — «координаты» подзадачи (что за подзадача)." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Переходы — как получить состояние из других (рекуррентная формула)." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Ответ — конкретное состояние, соответствующее исходной задаче (например, dp[n], dp[n][m], dp[mask_all][last])." }] } ] } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Примеры состояний и кода" }] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "1) Фибоначчи: dp[n] — n-е число" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Состояние: n. Храним: значение F(n). Переход: F(n)=F(n-1)+F(n-2). База: F(0)=0, F(1)=1." } ] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "// Top-down (мемоизация)\nconst fibMemo = (function () {\n const memo = new Map();\n memo.set(0, 0);\n memo.set(1, 1);\n function f(n) {\n if (memo.has(n)) return memo.get(n);\n const val = f(n - 1) + f(n - 2);\n memo.set(n, val);\n return val;\n }\n return f;\n})();\n\n// Bottom-up (табуляция)\nfunction fib(n) {\n if (n <= 1) return n;\n let a = 0, b = 1; // dp[n-2], dp[n-1]\n for (let i = 2; i <= n; i++) {\n const c = a + b;\n a = b;\n b = c;\n }\n return b;\n}\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "2) Количество путей в сетке с препятствиями: dp[i][j]" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Состояние: клетка (i, j). Храним: число путей до (i, j). Переход: dp[i][j]=dp[i-1][j]+dp[i][j-1], если нет препятствия. База: dp[0][0]=1, если старт без препятствия." } ] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "function uniquePathsWithObstacles(grid) {\n const m = grid.length, n = grid[0].length;\n const dp = Array.from({ length: m }, () => Array(n).fill(0));\n if (grid[0][0] === 1) return 0;\n dp[0][0] = 1;\n for (let i = 0; i < m; i++) {\n for (let j = 0; j < n; j++) {\n if (grid[i][j] === 1) { dp[i][j] = 0; continue; }\n if (i === 0 && j === 0) continue;\n const fromTop = i > 0 ? dp[i - 1][j] : 0;\n const fromLeft = j > 0 ? dp[i][j - 1] : 0;\n dp[i][j] = fromTop + fromLeft;\n }\n }\n return dp[m - 1][n - 1];\n}\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "3) 0/1 Рюкзак: dp[i][w]" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Состояние: (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." } ] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "function knapSack(capacity, weights, values) {\n const n = weights.length;\n const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));\n for (let i = 1; i <= n; i++) {\n for (let w = 0; w <= capacity; w++) {\n dp[i][w] = dp[i - 1][w]; // не берём i-й\n if (w >= weights[i - 1]) {\n dp[i][w] = Math.max(\n dp[i][w],\n dp[i - 1][w - weights[i - 1]] + values[i - 1]\n );\n }\n }\n }\n return dp[n][capacity];\n}\n\n// Оптимизация памяти (скользящий массив)\nfunction knapSack1D(capacity, weights, values) {\n const n = weights.length;\n const dp = Array(capacity + 1).fill(0);\n for (let i = 0; i < n; i++) {\n for (let w = capacity; w >= weights[i]; w--) {\n dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);\n }\n }\n return dp[capacity];\n}\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "4) DP по подмножествам (пример TSP): dp[mask][i]" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Состояние: (mask, i) — мы посетили набор вершин mask, находимся в i. Храним: минимальную стоимость пути. Переход: dp[mask][i] = min_j dp[mask \\ {i}][j] + cost[j][i]. База: dp[1< Array(n).fill(INF));\n dp[1 << start][start] = 0;\n for (let mask = 0; mask < N; mask++) {\n for (let i = 0; i < n; i++) {\n if ((mask & (1 << i)) === 0) continue;\n const cur = dp[mask][i];\n if (cur >= INF) continue;\n for (let j = 0; j < n; j++) {\n if (mask & (1 << j)) continue;\n const nextMask = mask | (1 << j);\n dp[nextMask][j] = Math.min(dp[nextMask][j], cur + cost[i][j]);\n }\n }\n }\n let ans = INF;\n for (let i = 0; i < n; i++) {\n ans = Math.min(ans, dp[N - 1][i] + cost[i][start]);\n }\n return ans;\n}\n" } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Оценка сложности через состояние" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Время ≈ (число состояний) × (среднее число переходов на состояние). Память ≈ число состояний (с учётом оптимизаций, например, скользящих массивов или компрессии масками)." } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Фибоначчи: O(n) состояний, O(1) переходов → O(n) времени, O(1)/O(n) памяти." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Рюкзак: O(n·W) состояний, O(1) переходов → O(n·W) времени, O(n·W) или O(W) памяти." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "TSP по маскам: O(n·2^n) состояний, O(n) переходов → O(n^2·2^n) времени, O(n·2^n) памяти." }] } ] } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Типичные ошибки при определении состояния" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Недостаточное состояние: не включили параметр, от которого зависит ответ (получаются неверные переиспользования)." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Избыточное состояние: добавили лишний параметр → взрыв размерности и ресурсов." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Неверный порядок обхода в bottom-up: используете ещё не посчитанные состояния." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Плохая инициализация: забыты базовые случаи, неверные значения по умолчанию (например, −∞/∞ вместо 0)." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Дублирование подзадач: неправильное кодирование состояния (например, неупорядоченные пары без нормализации)." }] } ] } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Краткий чек-лист по state в ДП" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Что храню в dp? (минимум/максимум/счёт/булево/лучшее)" }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Какие параметры однозначно описывают подзадачу? (индексы, флаги, маски…)" }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Есть оптимальная структура и корректные переходы?" }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Размерность приемлема по времени/памяти? (возможна ли компрессия)" }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Правильная инициализация и порядок вычисления выбраны?" }] } ] } ] } ] }

Что такое “state” (состояние) в DP?

Комментарии