動的計画法
01 / 共通の仕組み
表が 1 マスずつ自身を埋めていき、各マスは 定数個の以前のマスから合成される。 漸化式はサブパターンごとに異なるが、仕組み — 状態、遷移、埋める順序 — は共通している。
02 / 一文での本質
各添字は小さく固定された状態集合のひとつに属し、 状態間の遷移規則が明示されている。状態機械を入力に沿って展開 —— DP テーブルは状態ごとに 1 行、位置ごとに 1 列。
問題クールダウン付き株式の最大利益価格[1, 2, 3, 0, 2]
d0
$1
d1
$2
d2
$3
d3
$0
d4
$2
保有
·
·
·
·
·
売却
·
·
·
·
·
休息
·
·
·
·
·
日ごとに 3 つの状態:held(株を保有)、sold(今日売った —— 明日はクールダウン)、rest(未保有、買い可能)。日ごとに埋める。
ステップ
0 / 14
書き込み中
—
経由
—
最大利益
—
0 / 14
03 / パターンの骨格
# 状態機械 DP — 各状態の時系列を追うdp[state][0] ← 状態ごとの基底for i in 1..n−1:for each state:dp[state][i] ← state' からの合法遷移について max/min を取る(dp[state'][i−1] + cost(state'→state, input[i]))return 終端状態の中で dp[state][n−1] の最大# クールダウン:状態 = held / sold / rest# held[i] = max(held[i−1], rest[i−1] − price[i])# sold[i] = held[i−1] + price[i]# rest[i] = max(rest[i−1], sold[i−1])
04 / このパターンを使うべき合図
「有限のモード」
各位置での選択は、いまどのモードにいるかに依存する —— 保有しているかしていないか、連続かストリーク途切れか、残り取引回数。モードこそが状態。
「遷移の制約」
状態によっては許されない動きがある —— 売却後はまず休む必要がある、 2 回続けて飛ばせない、必ず交互にする。 不正な遷移が問題のルールを符号化し、合法な遷移が漸化式になる。
「終端での答えは状態ごと」
最終的な答えは、位置
n − 1 における終端状態同士の最良値。 多くの場合は「未保有」だが、「状態 X で終わらなければならない」と 題意が要求するなら、読むのは 1 行だけ。「状態数は小さな定数」
通常は 2〜5 個。状態数が入力に応じて増える場合(例:取引回数
k)、 DP に軸が 1 本増えて計算量は O(N · k) になる。05 / よくある落とし穴
i.
状態の欠落や重複。
状態がすべての可能な位置をきれいに分割できていないと、遷移が爆発して漸化式が曖昧になる。 自己点検:任意の時点における正当な位置は、ちょうど 1 つの状態に割り当てられるか?できないなら、コードを書く前に状態集合を作り直すこと。
ii.
状態ごとの基底が対称でない。
各状態は固有の 0 日目の値を持つ必要があり、すべて 0 ということはまずない。 クールダウンでは
held[0] = -price[0](今日買った)、sold[0] = rest[0] = 0(取引なし)。 基底での 1 ずれは、その後のすべてのセルに伝播する。iii.
状態間の暗黙の結合。
dp[B][i] を埋めるときに dp[A][i-1] を読むのは問題ないが、dp[A][i](同じ列)を読むと順序依存が生じる:同じ日 i 内で 状態 A を先に、B を後に埋めなければならない。必ず遷移グラフを描き、内側ループの順序がそれに従うようにする。06 / LeetCode で練習
状態機械 DP の 4 問。最初の 3 問は状態数とクールダウン/手数料のルールが異なる。 4 問目は分野が変わり、状態が「位置」ではなく「連続した選択」になる。
— / どれをいつ使うか
1 次元線形
添字 i での答えが、定数個の以前の添字にしか依存しない場合に使う。
家を盗む · 階段を登る · 最大部分和
2 次元グリッド
状態が2 つの添字を持つ場合 — グリッド、または相互作用する 2 つの列。
最短経路 · LCS · 編集距離
ナップサック
各アイテムが容量制約下で選ぶ / 飛ばすの判断を生む場合に使う。
部分集合和 · コイン · 分割
区間
状態が区間
(i, j) で、答えが内側の区間から合成される場合に使う。回文 · 行列連鎖 · 風船を割る
状態機械
各添字が複数の有限状態のいずれかにあり、状態間の遷移規則が決まっている場合に使う。
株 · クールダウン · 2 状態