フィボナッチ：再帰木 vs メモ化
同じ計算を何度もやり直す素朴な再帰が、「答えを覚えておく」だけで一気に枝刈りされる 様子を体感します。
計算する n
6
方式
実行ステップ（呼び出し順に展開）
1
素朴な再帰の呼び出し回数
—
メモ化の呼び出し回数
—
F(n) の値
—
計算するノード
基底（F0 / F1）
メモから即答（再計算しない）
いま展開中
フィボナッチ数列は
素朴に再帰すると、同じ
一度計算した値を表に控えておく メモ化 をすると、2 回目以降は表を引くだけ。これが 動的計画法（DP）の出発点です。
F(n) = F(n-1) + F(n-2)、F(0)=0, F(1)=1 で定義されます。素朴に再帰すると、同じ
F(k) を何度も計算し直して 呼び出し回数が指数的に爆発します。一度計算した値を表に控えておく メモ化 をすると、2 回目以降は表を引くだけ。これが 動的計画法（DP）の出発点です。
いま何が起きている？
ここが DP の本質
- 素朴な再帰は 部分問題
F(k)を何度も解き直す。木の同じ形があちこちに現れる。 - メモ化は 部分問題の答えを 1 度だけ計算して覚えておく。木の重複した枝がまるごと消える。
- 呼び出し回数は素朴で約
2·F(n+1)（指数的）、メモ化で2n−1（線形）。 - 「部分問題の解を覚えておく」── これがナップサックや LCS など、すべての DP に共通する考え方です。