動的計画法
01 / 共通の仕組み
表が 1 マスずつ自身を埋めていき、各マスは 定数個の以前のマスから合成される。 漸化式はサブパターンごとに異なるが、仕組み — 状態、遷移、埋める順序 — は共通している。
02 / 一文での本質
状態は区間(i, j)。答えは[i, j]の内側にあるより小さな区間から組み立てられる。 行ごとではなく区間長を増やしながら埋める — これだけが依存先がそろっていることを保証する方向。
問題最長回文部分文字列入力"babad"n5
b0
a1
b2
a3
d4
0
1
2
3
4
0
·
·
·
·
·
1
·
·
·
·
2
·
·
·
3
·
·
4
·
各 dp[i][j] は「s[i..j] は回文か?」に答える。区間長順に埋める —— まず 1、次に 2、次に 3、……
ステップ
0 / 12
区間長
—
最良長
1
最良区間
[0, 0]
0 / 12
03 / パターンの骨格
# 区間 DP — 行ではなく長さで埋める# 基底:長さ 1(多くの場合は長さ 2 も)for len in 2..n:for i in 0..n−len:j ← i + len − 1dp[i][j] ← f(dp[i+1][j−1], ...) または (i, j) 内の k で分割return dp[0][n−1]# 回文:dp[i][j] = (s[i]==s[j]) AND dp[i+1][j−1]# 行列連鎖:(i, j) 内の k での最小 dp[i][k] + dp[k+1][j] + cost
04 / このパターンを使うべき合図
「区間に対するクエリ」
任意の連続部分配列や部分文字列の性質を問う問題 —— 回文、整列、平衡。部分区間が第一級の対象。
「内から外へ組み立てる」
[i, j] の答えは厳密に内側の区間だけに依存する —— [i+1, j-1]、または [i, k] + [k+1, j]。 再帰は外側からむいていく。「分割点の探索」
行列連鎖、風船割り、最適 BST ——
(i, j) 内のすべての k を試して合成する。この内側ループが計算量を O(N²) から O(N³) に押し上げる。「上三角テーブル」
意味があるのは
i ≤ j のセルだけ —— 半分は使われない。 埋める順序は対角線に沿う:主対角線(長さ 1)、次の対角線(長さ 2)、外側へ。05 / よくある落とし穴
i.
長さごとではなく行ごとに埋めてしまう。
i を外側、j を内側にすると、dp[i+1][j-1] がまだ埋まらないうちにそれを読もうとしてしまう —— そのセルは i+1 行に属し、その行はまだ来ていない。 正解は長さを外側にすること。長さ L の区間がすべて完了してから、 長さ L+1 の区間に触れる。ii.
長さ 2 を独立した基底として忘れる。
回文では、
dp[i][i+1] = (s[i] == s[i+1]) は一般の漸化式からは出てこない。dp[i+1][i] は対角線の下 —— 不正な区間であって false ではないからだ。きれいな実装は長さ 2 を長さ 1 と並ぶ別個の基底として扱う。iii.
「分割点」型の区間 DP で分割の粒度を間違える。
行列連鎖や風船割りでは、分割点
k は (i, j) の内部 の添字を動く必要がある —— そして k の意味(左半分は [i, k] か [i, k-1] か)は問題ごとに異なる。 ここで 1 ずれると全体が壊れる。06 / LeetCode で練習
区間 DP の 4 問。最初の 2 問は内部区間を直接読む漸化式(長さ 2 で飛ぶ)。 後ろの 2 問は分割点の探索が必要 —— (i, j) 内のすべての k が候補になる。
— / どれをいつ使うか
1 次元線形
添字 i での答えが、定数個の以前の添字にしか依存しない場合に使う。
家を盗む · 階段を登る · 最大部分和
2 次元グリッド
状態が2 つの添字を持つ場合 — グリッド、または相互作用する 2 つの列。
最短経路 · LCS · 編集距離
ナップサック
各アイテムが容量制約下で選ぶ / 飛ばすの判断を生む場合に使う。
部分集合和 · コイン · 分割
区間
状態が区間
(i, j) で、答えが内側の区間から合成される場合に使う。回文 · 行列連鎖 · 風船を割る
状態機械
各添字が複数の有限状態のいずれかにあり、状態間の遷移規則が決まっている場合に使う。
株 · クールダウン · 2 状態