動的計画法
01 / 共通の仕組み
表が 1 マスずつ自身を埋めていき、各マスは 定数個の以前のマスから合成される。 漸化式はサブパターンごとに異なるが、仕組み — 状態、遷移、埋める順序 — は共通している。
02 / 一文での本質
状態は2 つの添字を持ち、(i, j) での答えは厳密に小さい座標を持つ定数個のセルから組み立てられる — 行ごとに埋めれば、各セルに到達したときには依存先がすべて表に揃っている。問題左上 → 右下の最小経路和グリッド3×3
1?
3?
1?
1?
5?
1?
4?
2?
1?
各 dp[i][j] は (0,0) から (i,j) までの最小コスト経路。行ごとに埋める。
ステップ
0 / 10
埋めたセル
0
選択
—
最小経路和
—
0 / 10
03 / パターンの骨格
# 2 次元 DP — 2 つの添字、近隣セルの読み取りdp[0][0] ← 基底ケース# 先頭行と先頭列を累積で埋める(1 次元の基底)for i in 1..R−1:for j in 1..C−1:dp[i][j] ← f(dp[i−1][j], dp[i][j−1], dp[i−1][j−1])return dp[R−1][C−1]# 最小経路和: f = grid[i][j] + min(top, left)# LCS: f = (s1[i]==s2[j]) ? diag+1 : max(top, left)# 編集距離: f = (s1[i]==s2[j]) ? diag : 1 + min(top, left, diag)
04 / このパターンを使うべき合図
「グリッド」
状態がそのままグリッド座標 — 右/下にのみ移動可能 が典型形。 依存の矢印は常に後ろ向きで、横や上向きには伸びない。
「2 つの列」
問題に2 つの文字列または2 つの配列が現れ、 アライメント、共通構造、変換を問うとき — LCS、編集距離、正規表現マッチ。 状態
(i, j) = 「s1 の最初の i 文字、s2 の最初の j 文字」。「読むのは高々 3 つの近隣」
上、左、左上の対角。遠くのセルを読む必要があるなら DP の定式化が間違っている— おそらく別の状態か別の埋め順が必要。
「答えは隅にある」
最適解は
dp[R−1][C−1](または漸化式が終わる場所)に存在する。 表の途中で答えが求められる場合は、通常、表全体での最大値を追跡する必要がある。05 / よくある落とし穴
i.
埋め順が依存方向に違反する。
漸化式が、どのセルを先に書くべきかを決める。
dp[i][j]が上と左を読むなら、標準的な行ごと左から右の走査でよい。 だが回文部分文字列系の DP では、区間長の順に埋める必要がある。常に問え:依存先は表の中で今の位置に対しどこにあるのか?ii.
入力と表で添字が 1 ずれる。
表のサイズが
(M+1) × (N+1)(双系列 DP でよくある)のとき、 入力の添字と表の添字は 1 つずれる。 デバッグ時間の大半は、このずれた 1 のバグに費やされる。iii.
ローリング行最適化が不可逆だと忘れる。
1 行に圧縮すれば空間は
O(R·C) から O(C) に落ちるが、経路は失われる — 最終コストだけ残る。 実際の経路(最小経路和の具体的なセル列、LCS 文字列そのものなど)も求められるなら、 表全体を保持する。06 / LeetCode で練習
4 問、2 次元表の組み立て方順に並べた。最初の 2 つは文字通りのグリッド。 残り 2 つは双系列 DP で、グリッドは概念上のもの — 行は片方の文字列の位置、列はもう片方の文字列の位置。
— / どれをいつ使うか
1 次元線形
添字 i での答えが、定数個の以前の添字にしか依存しない場合に使う。
家を盗む · 階段を登る · 最大部分和
2 次元グリッド
状態が2 つの添字を持つ場合 — グリッド、または相互作用する 2 つの列。
最短経路 · LCS · 編集距離
ナップサック
各アイテムが容量制約下で選ぶ / 飛ばすの判断を生む場合に使う。
部分集合和 · コイン · 分割
区間
状態が区間
(i, j) で、答えが内側の区間から合成される場合に使う。回文 · 行列連鎖 · 風船を割る
状態機械
各添字が複数の有限状態のいずれかにあり、状態間の遷移規則が決まっている場合に使う。
株 · クールダウン · 2 状態