動的計画法
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 / よくある落とし穴
状態の欠落や重複。
状態がすべての可能な位置をきれいに分割できていないと、遷移が爆発して漸化式が曖昧になる。 自己点検:任意の時点における正当な位置は、ちょうど 1 つの状態に割り当てられるか?できないなら、コードを書く前に状態集合を作り直すこと。
状態ごとの基底が対称でない。
各状態は固有の 0 日目の値を持つ必要があり、すべて 0 ということはまずない。 クールダウンでは
held[0] = -price[0](今日買った)、sold[0] = rest[0] = 0(取引なし)。 基底での 1 ずれは、その後のすべてのセルに伝播する。状態間の暗黙の結合。
dp[B][i] を埋めるときに dp[A][i-1] を読むのは問題ないが、dp[A][i](同じ列)を読むと順序依存が生じる:同じ日 i 内で 状態 A を先に、B を後に埋めなければならない。必ず遷移グラフを描き、内側ループの順序がそれに従うようにする。06 / LeetCode で練習
中級13
01Decode Ways— LC 91→02Best Time to Buy and Sell Stock II— LC 122→03House Robber— LC 198→04House Robber II— LC 213→05Paint House— LC 256→06Paint Fence— LC 276→07Best Time to Buy and Sell Stock with Cooldown— LC 309→08Best Time to Buy and Sell Stock with Transaction Fee— LC 714→09Delete and Earn— LC 740→10Online Stock Span— LC 901→11Knight Dialer— LC 935→12Prison Cells After N Days— LC 957→13Number of Ways to Select Buildings— LC 2222→
難しい9
01Best Time to Buy and Sell Stock III— LC 123→02Best Time to Buy and Sell Stock IV— LC 188→03Paint House II— LC 265→04Student Attendance Record II— LC 552→05Number of Music Playlists— LC 920→06Distinct Subsequences II— LC 940→07Handshakes That Don't Cross— LC 1259→08Number of Ways to Paint N x 3 Grid— LC 1411→09Paint House III— LC 1473→
— / どれをいつ使うか
1 次元線形
添字 i での答えが、定数個の以前の添字にしか依存しない場合に使う。
家を盗む · 階段を登る · 最大部分和
2 次元グリッド
状態が2 つの添字を持つ場合 — グリッド、または相互作用する 2 つの列。
最短経路 · LCS · 編集距離
ナップサック
各アイテムが容量制約下で選ぶ / 飛ばすの判断を生む場合に使う。
部分集合和 · コイン · 分割
区間
状態が区間
(i, j) で、答えが内側の区間から合成される場合に使う。回文 · 行列連鎖 · 風船を割る
状態機械
各添字が複数の有限状態のいずれかにあり、状態間の遷移規則が決まっている場合に使う。
株 · クールダウン · 2 状態
木 DP
問題が木上にあり、各ノードの答えが子ノードの答えに依存する場合に使う。
家強盗 III · 直径 · 最大経路和
ビットマスク
状態が部分集合(通常
N ≤ 20)で、どのアイテムを選んだかだけが重要で順序は問わない場合に使う。割り当て · TSP · 最小十分チーム