1. なぜ遅いのか — フィボナッチの再帰木が爆発する
フィボナッチ数 f(n) = f(n−1) + f(n−2) を、定義そのままに再帰で書くと自然に見えます。ところがこの素朴な再帰は、まったく同じ小問題を何度も何度も解き直して います。下の木で、同じ色（＝同じ f の値）のマルがいくつ現れるかを数えてみてください。
「メモ化あり」に切り替えると、一度計算した値は表から即座に返す ようになり、木がばっさり刈り込まれます。呼び出し回数が指数から直線へ変わる瞬間です。
フィボナッチの再帰木 — 素朴な再帰 vs メモ化
同じ色のマル＝まったく同じ小問題 f(k)。素朴な再帰では f(2) や f(3) が何度も再計算され、木の大きさは n に対して指数的に増えます。「済」の灰色ノードは、メモ化で「表にもう答えがある」ため展開せず打ち切った枝です。右上の比較を見ると、n を1増やすたびに素朴版だけが爆発します。
POINT — DPが効くための2条件
動的計画法が使えるのは、問題が次の2つを満たすとき。①部分構造最適性 ：大きな問題の最適解が、小さな部分問題の最適解から組み立てられる。②部分問題の重複 ：同じ小問題が何度も現れる。フィボナッチはまさに②の典型で、だから「一度解いたら表に貯める」が劇的に効く。
素朴な再帰: 呼び出し ≈ 2 f(n+1) − 1（指数的） → メモ化: 呼び出し 2n − 1（線形）
同じ漸化式でも、答えを記録するかどうかで計算量が O(φn ) から O(n) へ激変する
2. 表に貯めれば一直線 — メモ化とボトムアップ
再帰木を上から掘り進むのが「メモ化（トップダウン）」なら、逆に小さいほうから表を順に埋めていく のが「ボトムアップ」です。フィボナッチなら dp[0], dp[1] を種にして、左から右へ dp[i] = dp[i−1] + dp[i−2] を1マスずつ計算するだけ。二度と枝分かれしません。
下のデモで ▶ 再生 または 1マス進む を押し、表が左から順に埋まる様子を見てください。いま計算中のマスが、直前の2マスだけを参照しているのがわかります。
ボトムアップDP — 表を左から1マスずつ埋める
緑＝計算済み、オレンジ＝いま計算中のマス、水色枠＝そのマスが参照する直前の2マス。上の式が「今のマス = 直前2マスの和」を実況します。参照するのが常に2マスだけなので、全体は n 回の足し算 ＝ O(n) で終わります。
3. 2次元の表 — 0-1ナップサック問題
DPの真価は2次元以上で発揮されます。0-1ナップサック問題 ：重さの上限がある袋に、価値の合計が最大になるよう品物を詰める（各品物は入れる／入れないの二択）。表の行＝使える品物を1つずつ増やし、列＝袋の残り容量。マス dp[i][c] は「最初の i 個の品物と容量 c で得られる最大価値」です。
各マスは「今の品物を入れない」か「入れる」かの大きいほう を選ぶだけ。上のマスと、斜め上（容量を品物の重さぶん戻したマス＋価値）を見比べます。埋め終わったら、選ばれた品物を逆にたどって浮かび上がらせます。
0-1ナップサック — 表を行ごとに埋め、選んだ品物を復元する
左の列＝品物（🎒重さ/価値）、上の行＝容量0〜。オレンジ＝計算中のマス、水色＝「入れない場合」（真上）、紫＝「入れる場合」（斜め上＋価値）の参照元。両者の大きいほうを採用します。全マスが埋まると、右下の最適値から矢印で選ばれた品物 を逆算し、緑で強調します。
dp[i][c] = max( dp[i−1][c], dp[i−1][c − wi ] + vi )
前者＝品物 i を入れない、後者＝入れる（容量を wi 戻して価値 vi を足す）。wi > c なら入れられないので前者のみ
注意 — 「多項式時間」に見えて実は擬多項式
ナップサックDPの計算量は O(品物数 × 容量) で一見速い。だが「容量」は数値そのものであり、入力のビット長 に対しては指数的になりうる（容量が10億なら表も10億列）。これを擬多項式時間 と呼ぶ。実際0-1ナップサックはNP困難で、真に効率的な厳密解法は知られていない — 次のレッスンの主役です。
4. 経過をたどる — 編集距離とトレースバック
2つの文字列がどれだけ「違う」かを測るのが編集距離（レーベンシュタイン距離） 。1文字の挿入・削除・置換 を何回で一方をもう一方に変えられるか、の最小値です。スペルチェッカ・DNA配列比較・diffツールの心臓部でもあります。
グリッドのマス dp[i][j] は「a の先頭 i 文字を b の先頭 j 文字に変える最小手数」。各マスは3方向（上＝削除、左＝挿入、斜め＝置換 or 一致）の最小＋1 で決まります。文字が一致するときは斜めをコスト0で通れる。埋め終えたら、右下から左上へ最小コストの道 を逆にたどると、実際の編集手順が現れます。
編集距離グリッド — 3方向の最小を選び、道を逆にたどる
単語ペア
kitten → sitting
sunday → saturday
flaw → lawn
1マス進む ▸
↺ 最初から
⏸ 一時停止
左に a、上に b の文字を並べます。オレンジ＝計算中のマスで、上（削除）・左（挿入）・斜め（置換／一致）の3つの参照元を色で示します。文字が一致するマスは斜めをコスト0で通れるため、緑の「一致」印が付きます。完成後、右下の答えから左上への最短の道 を黄色でたどると、必要な編集操作の並びが読み取れます。
dp[i][j] = min( dp[i−1][j] + 1, dp[i][j−1] + 1, dp[i−1][j−1] + [ai ≠ bj ] )
上から削除、左から挿入、斜めから置換。文字が同じ [ai =bj ] なら斜めは +0 で通れる
POINT — DP設計の3ステップ
新しい問題をDPで解くときの型はいつも同じ。①状態を決める （表の各マスが「何の最適値」を表すか）。②漸化式を書く （そのマスをより小さいマスからどう作るか）。③埋める順序を決める （参照するマスが先に埋まる順に回す）。この3つが書ければ、あとは二重ループで表を埋めるだけ。
5. まとめ — 「解いたら書き留める」の破壊力
部分問題の重複 があるとき、素朴な再帰は同じ計算を指数回くり返す。フィボナッチが好例。メモ化（トップダウン） とボトムアップ は同じDPの表裏。前者は必要な部分だけ、後者は全マスを順に埋める。状態・漸化式・順序 の3点を決めれば、1次元（フィボナッチ）も2次元（ナップサック・編集距離）も同じ手つきで解ける。DPで多項式時間に落ちても、ナップサックの容量のように擬多項式 に留まる問題があり、それが計算の限界の話へつながる。
一歩先へ — DPは至るところに潜んでいる
最短経路のベルマン–フォード、音声認識・HMMのビタビ復号、生物情報学の配列アラインメント、正規表現マッチ、そして強化学習の価値反復（ベルマン方程式）——これらはすべて「部分問題の表を最適に埋める」同じDPの化身だ。前回の貪欲法が「表を作らず最初の1手を確定できる特別なDP」だったことを思い出すと、貪欲・分割統治・DPが一枚の地図の上に並ぶ。次回はこの地図の外側、DPでも歯が立たない問題 の世界へ踏み込む。