動的計画法
01 / 共通の仕組み
表が 1 マスずつ自身を埋めていき、各マスは 定数個の以前のマスから合成される。 漸化式はサブパターンごとに異なるが、仕組み — 状態、遷移、埋める順序 — は共通している。
01 / 一文での本質
1 次元の表の各セルは、同じ問題のより小さな版に対する答え — 順序通りに 1 度だけ埋めれば、任意の位置の答えは定数個の 先行セルから組み立てられる。
問題非隣接な家からの最大の戦利品入力[2, 7, 9, 3, 1, 8]
input
20
71
92
33
14
85
dp
?0
?1
?2
?3
?4
?5
各 dp[i] は家 0..i までを考慮したときの最大の戦利品。左から右へ埋める。
ステップ
0 / 7
i
—
選択
—
ここまでの最大
0
0 / 7
02 / パターンの骨格
# 1 次元 DP — 各ステップで 2 つの選択肢から 1 つを選ぶdp[0] ← 基底ケース 0dp[1] ← 基底ケース 1for i in 2..n−1:dp[i] ← f(dp[i−1], dp[i−2], input[i])return dp[n−1]# house robber: f = max(dp[i−1], dp[i−2] + nums[i])# 最大部分配列 (Kadane): f = max(nums[i], dp[i−1] + nums[i])# 階段上り: f = dp[i−1] + dp[i−2]
03 / このパターンを使うべき合図
「最大 / 最小 / 個数」
最適化または数え上げで、位置
i の答えがより小さな位置の答えから組み立てられる。 素朴解が指数時間なら、DP を疑え。「非隣接 / 列」
位置に関する制約 — 隣を選べない、順序を保つ、部分列を成す。 各ステップの選択は、より前の選択と影響し合う。
「重複部分問題」
素朴な再帰は同じ小さな部分問題を何度も解く。DP はキャッシュする。
「最適部分構造」
位置
i での最適解は、より小さな添字での最適解から構成される — 任意の答えではない。 これが無ければ貪欲は誤りだが、DP も助けにならない。04 / よくある落とし穴
i.
基底ケースを取り違える。
dp[0] と dp[1] は 1 ずれが最も生じやすい場所。声に出して読む: 「要素が1 つのときの答え」「要素が2 つのときの答え」。 ループを書く前に、最小の非自明な入力で確認する。ii.
反復方向を間違える。
漸化式が埋める順序を決める —
dp[i+1] がまだ書かれていないうちに読むことはできない。 左から右が既定だが、問題によっては(例えば棒切り問題の双対形)右から左が必要。iii.
DP が必要な場面で貪欲に手を伸ばす。
各ステップで局所最適を取ると、より良い大域解への道が閉ざされる場合 (例:「今この小さな家を盗む」と「2 つ先の大きな家を盗む」を失う)、貪欲は破綻する。 DP は両方の分岐を考慮し、最大値を取る。
05 / LeetCode で練習
4 問、それぞれの漸化式の所在順に並べた。最初の 3 つは 1 次元線形 DP。 4 つ目で O(N²) DP に持ち上がる — 表は依然 1 次元だが、依存範囲がより広い。
— / どれをいつ使うか
1 次元線形
添字 i での答えが、定数個の以前の添字にしか依存しない場合に使う。
家を盗む · 階段を登る · 最大部分和
2 次元グリッド
状態が2 つの添字を持つ場合 — グリッド、または相互作用する 2 つの列。
最短経路 · LCS · 編集距離
ナップサック
各アイテムが容量制約下で選ぶ / 飛ばすの判断を生む場合に使う。
部分集合和 · コイン · 分割
区間
状態が区間
(i, j) で、答えが内側の区間から合成される場合に使う。回文 · 行列連鎖 · 風船を割る
状態機械
各添字が複数の有限状態のいずれかにあり、状態間の遷移規則が決まっている場合に使う。
株 · クールダウン · 2 状態