動的計画法
01 / 共通の仕組み
表が 1 マスずつ自身を埋めていき、各マスは 定数個の以前のマスから合成される。 漸化式はサブパターンごとに異なるが、仕組み — 状態、遷移、埋める順序 — は共通している。
02 / 一文での本質
各アイテムが取るか飛ばすかの決定を引き起こし、状態はこれまでに 積み上げたもの全て — 通常は和または容量。 2 次元表は一方の軸にアイテム、もう一方に累積状態を置く。
問題2 つの等和部分集合への分割入力[1, 5, 11, 5]目標11
アイテム
10
51
112
53
和 →01234567891011
∅
·
·
·
·
·
·
·
·
·
·
·
·
+1
·
·
·
·
·
·
·
·
·
·
·
·
+5
·
·
·
·
·
·
·
·
·
·
·
·
+11
·
·
·
·
·
·
·
·
·
·
·
·
+5
·
·
·
·
·
·
·
·
·
·
·
·
合計 = 22、目標 = 11。各 dp[i][s] は「最初の i 個のアイテムで和 s を作れるか?」に答える。
ステップ
0 / 50
目標
11
選択
—
答え
—
0 / 50
03 / パターンの骨格
# ナップサック — アイテムごとに取る/飛ばすdp[0][0] ← 基底ケース(多くは true / 0)for i in 1..n:for s in 0..target:skip ← dp[i−1][s]take ← if s ≥ w[i]: dp[i−1][s−w[i]] else falsedp[i][s] ← combine(skip, take)return dp[n][target]# 部分和: combine = OR;0/1 ナップサック: combine = max# 無制限(コイン): dp[i−1][s−w] ではなく dp[i][s−w] を読む
04 / このパターンを使うべき合図
「部分集合を選ぶ」
アイテムのある部分集合が制約を満たすか、または予算下で最適な部分集合を問う問題。アイテムの順序が関係ないなら、ナップサックを疑え。
「重量 / 容量 / 目標」
数値の予算(容量、和、個数)が選択を制限する。この予算が DP 表の第 2 軸になる。
「各アイテムは一意」
標準の 0/1 ナップサック:各アイテムは最大 1 回まで取れる。再利用可能なら無制限ナップサック(コイン交換)の領域 — 漸化式は前の行ではなく現在の行から読む。
「状態が 2 軸を持つ」
(処理したアイテム数、これまでの和)や(処理したアイテム数、使った容量)。 自然な状態が 2 軸より多くなると家族は変形するが、取る/飛ばすの骨格は残る。
05 / よくある落とし穴
i.
0/1 と無制限を取り違える。
0/1 ナップサックは
dp[i-1][s-w](前の行)を読む — 各アイテムは最大 1 回。 無制限は dp[i][s-w](現在の行)を読む — アイテムは繰り返し可。 1 次元配列に圧縮すると、0/1 は右から左に走査し、無制限は左から右に走査する。逆にすると、表は無言で誤った答えを出す。ii.
合計が奇数のときの短絡を忘れる。
部分集合の等分は合計が偶数である必要がある — 奇数は即座に不可能。 DP を走らせる前にこれを捕まえれば、入力の半分について
O(N · S)の作業を省ける。iii.
擬多項式時間の罠。
実行時間は
O(N · S)、ここで S は数値の目標 — 目標の log ではない。N が小さいが和が巨大な入力(例:[10^9])では、ナップサック DP は実行不能になる。これを見抜いて 別のアプローチ(出会いの折半、分枝限定)に切り替える。06 / LeetCode で練習
ナップサック家族の 4 問。最初の 3 つは combine の規則(OR、個数、最大)が異なる。 4 つ目は無制限へ移る — 骨格は同じで、現在行を読む。
— / どれをいつ使うか
1 次元線形
添字 i での答えが、定数個の以前の添字にしか依存しない場合に使う。
家を盗む · 階段を登る · 最大部分和
2 次元グリッド
状態が2 つの添字を持つ場合 — グリッド、または相互作用する 2 つの列。
最短経路 · LCS · 編集距離
ナップサック
各アイテムが容量制約下で選ぶ / 飛ばすの判断を生む場合に使う。
部分集合和 · コイン · 分割
区間
状態が区間
(i, j) で、答えが内側の区間から合成される場合に使う。回文 · 行列連鎖 · 風船を割る
状態機械
各添字が複数の有限状態のいずれかにあり、状態間の遷移規則が決まっている場合に使う。
株 · クールダウン · 2 状態