動的計画法
01 / 共通の仕組み
表が 1 マスずつ自身を埋めていき、各マスは 定数個の以前のマスから合成される。 漸化式はサブパターンごとに異なるが、仕組み — 状態、遷移、埋める順序 — は共通している。
02 / 一文で言うと
後順 DFS を実行する —— 親より先に両方の子を解決する。各ノードは値のペアを返す： このノードを盗んだ場合の最大収益と、スキップした場合の最大収益。
問題隣接なしで盗める最大金額木[3, 4, 5, 1, 3, -, 1]
二分木上の後順 DP — 各ノードは両方のサブツリーが rob / skip ペアを返してから計算する。
ステップ
0 / 7
ノード
—
rob
—
skip
—
答え
—
0 / 7
03 / パターンの骨格
# 木 DP — 後順、各ノードが (rob, skip) を返すfunction dp(node):if node is null: return (0, 0)(lr, ls) ← dp(node.left) # まず左を再帰(rr, rs) ← dp(node.right) # 次に右を再帰rob ← node.val + ls + rs # このノードを取り、子をスキップskip ← max(lr, ls) + max(rr, rs) # 各子から最良を選択return (rob, skip)lr, ls ← dp(root)answer ← max(lr, ls)
04 / このパターンを使うべき合図
「後順は必須」
両方の子が解決するまで、親は決定を下せない。前順や中順では子の値を推測するしかない。 後順はボトムアップ計算のための自然な走査順。
「1 値でなくペアを返す」
ノードごとにスカラー 1 つでは不十分 — 親は両方の結果（rob と skip）を知って 初めて自分の判断ができる。ペアを返すことが、サブツリーと親の間の最小インターフェース。
「null の基底 (0, 0)」
null の子は rob にも skip にも 0 を返す。これにより漸化式が均一になる — 葉ノードや片方の子しかないノードをループ本体で特別扱いする必要がない。基底値がきれいに伝播する。
「rob/skip を超えた一般化」
ノードの最適値が子の最適値に依存する問題はすべてこの形になる：後順 DFS、 小さな固定タプルを返す、親で合成する。直径（根を通る最長パス vs 通らない）、 最大経路和、木のカメラ設置、すべて同じ骨格を持つ。
05 / よくある落とし穴
戻り値の代わりにハッシュマップやグローバルメモを使う。
よくある間違い：
dp をノードから値へのハッシュマップとして定義し、 メモ化再帰でトップダウンに埋める。これは動くが、ボトムアップ構造が隠れる。 戻り値アプローチの方が明確 — データフローが可視化され、O(N) のメモ空間ではなく O(H) のスタック空間を使う。完全なペアではなく最終答えだけを返す。
dp(node) = max(rob, skip) として 1 つの数値だけを返すと、 親は 2 つのケースを区別できなくなり、誤った遷移が生じる。例えば、 子の答えが常に「スキップ」だと誤解して二重計上が起きる。 根に到達するまで必ず完全なペアを返すこと。子を合成するときどの値を使うかを混同する。
rob(node) = val + skip(left) + skip(right) — 子の skip 値を加える （rob 値ではない）。親を盗むと子を盗めないから。skip(node) = max(rob(L), skip(L)) + max(rob(R), skip(R)) — 各子が独立に最良を選ぶ。 この 2 つの漸化式を入れ替えるのはよくある間違いで、答えが狂う。06 / LeetCode で練習
中級16
01Unique Binary Search Trees II— LC 95→02Unique Binary Search Trees— LC 96→03House Robber III— LC 337→04Path Sum III— LC 437→05Longest Univalue Path— LC 687→06All Possible Full Binary Trees— LC 894→07Distribute Coins in Binary Tree— LC 979→08Smallest String Starting From Leaf— LC 988→09Tree Diameter— LC 1245→10Maximum Product of Splitted Binary Tree— LC 1339→11Longest ZigZag Path in a Binary Tree— LC 1372→12Count Good Nodes in Binary Tree— LC 1448→13Diameter of N-Ary Tree— LC 1522→14Number of Good Leaf Nodes Pairs— LC 1530→15Most Profitable Path in a Tree— LC 2467→16Minimum Score of a Path Between Two Cities— LC 2492→
難しい7
01Binary Tree Maximum Path Sum— LC 124→02Sum of Distances in Tree— LC 834→03Binary Tree Cameras— LC 968→04Number of Ways to Reorder Array to Get Same BST— LC 1569→05Longest Path With Different Adjacent Characters— LC 2246→06Difference Between Maximum and Minimum Price Sum— LC 2538→07Count Number of Possible Root Nodes— LC 2581→
— / どれをいつ使うか
1 次元線形
添字 i での答えが、定数個の以前の添字にしか依存しない場合に使う。
家を盗む · 階段を登る · 最大部分和
2 次元グリッド
状態が2 つの添字を持つ場合 — グリッド、または相互作用する 2 つの列。
最短経路 · LCS · 編集距離
ナップサック
各アイテムが容量制約下で選ぶ / 飛ばすの判断を生む場合に使う。
部分集合和 · コイン · 分割
区間
状態が区間
(i, j) で、答えが内側の区間から合成される場合に使う。回文 · 行列連鎖 · 風船を割る
状態機械
各添字が複数の有限状態のいずれかにあり、状態間の遷移規則が決まっている場合に使う。
株 · クールダウン · 2 状態
木 DP
問題が木上にあり、各ノードの答えが子ノードの答えに依存する場合に使う。
家強盗 III · 直径 · 最大経路和
ビットマスク
状態が部分集合(通常
N ≤ 20)で、どのアイテムを選んだかだけが重要で順序は問わない場合に使う。割り当て · TSP · 最小十分チーム