メモ化フィボナッチ
メモ化フィボナッチ
このレッスンで分かること
- メモ化は「部分問題の解を覚える」という DP の本質を最もシンプルに体験できる形
- このレッスンでは、フィボナッチ数列
fib(n) = fib(n-1) + fib(n-2)をメモ化で実装し、O(2^n)だった計算量をO(n)まで落とします- 再帰で書いた
fib(n)は美しい一方で、nが大きくなると一瞬で計算が終わらなくなります
メモ化フィボナッチ とは
再帰で計算したフィボナッチ数列の途中結果をキャッシュし、指数関数的な計算量を線形に減らす「メモ化」の手法を学ぶ。
再帰で書いた fib(n) は美しい一方で、n が大きくなると一瞬で計算が終わらなくなります。原因は 同じ部分問題を何度も解いてしまうこと。これを解消するのが メモ化 (memoization) です。一度計算した結果を辞書や配列に保存し、再度同じ引数で呼ばれたら計算せずに値を取り出す。動的計画法 の第一歩と言える基本パターンです。
このレッスンでは、フィボナッチ数列 fib(n) = fib(n-1) + fib(n-2) をメモ化で実装し、O(2^n) だった計算量を O(n) まで落とします。本章を通じて何度も登場する考え方なので、ここでしっかり手に馴染ませましょう。
再帰の遅さの正体は「同じ計算の重複」。メモ化はそれを 1 回で済ませる仕組み。
なぜ素朴な再帰は遅いのか
fib(5) を素朴に展開すると、fib(4) + fib(3) になり、fib(4) はまた fib(3) + fib(2) を呼びます。木のように分岐していく途中で、fib(3) や fib(2) が 何度も 同じ値を計算し直していることが分かります。具体的には fib(n) の呼び出し回数はおよそ φ^n (φ≈1.618) のオーダーで膨らみます。n = 40 で約 3 億回以上になり、これでは現実的な時間で終わりません。
図のポイント (テキスト併記)
- 図を見ると
fib 3が 2 回、fib 2が 3 回呼ばれていることが分かります
図を見ると fib 3 が 2 回、fib 2 が 3 回呼ばれていることが分かります。n が 1 増えるたびに呼び出し回数はおよそ 2 倍になっていく、これが指数的爆発の正体です。
同じ
fib 3を 2 回計算するなら、初回の結果を覚えておけば 2 回目はゼロコストで返せる。
メモ化の発想
やることはとてもシンプルです。結果を保存する辞書 (もしくは配列) を用意し、関数を呼ぶ前にそこを覗いて、答えがあれば返す。なければ計算してから記録する。たったこれだけで、各 n の計算は 1 回しか実行されなくなります。
計算量を見直すと、fib(0)、fib(1)、…、fib(n) の n+1 個の部分問題 をそれぞれ 1 回ずつ解くだけなので O(n) です。n = 40 でも 40 回程度で終わり、ミリ秒もかかりません。
Python での実装
Python
def fibMemo(n):
memo = {}
def helper(k):
if k < 2:
return k
if k in memo:
return memo[k]
memo[k] = helper(k - 1) + helper(k - 2)
return memo[k]
return helper(n)クロージャの中で memo 辞書を共有しています。memo[k] に既に値があるなら即 return、なければ再帰で計算してから保存する流れです。functools.lru_cache を使えば 1 行で書けますが、まずは原理を写経してください。
JavaScript での実装
JavaScript
function fibMemo(n) {
const memo = new Map();
function helper(k) {
if (k < 2) return k;
if (memo.has(k)) return memo.get(k);
const v = helper(k - 1) + helper(k - 2);
memo.set(k, v);
return v;
}
return helper(n);
}JavaScript では Map を使うのが定番です。オブジェクトでも動きますがキーが文字列化されてしまうため、整数キーには Map が安全です。
よくある間違い
1 つ目は 基底ケースの取り違え。fib(0) = 0、fib(1) = 1 を if k < 2: return k の 1 行でまとめて表現していますが、fib(0) = 1 から始めるバリアントもあるので、問題文に合わせて確認しましょう。2 つ目は memo の初期化忘れ。グローバルに置くと別の呼び出しで値が残って汚染されることがあります。3 つ目は 再帰の深さ制限。Python はデフォルトで再帰深さが 1000 なので、n = 10000 のような巨大入力ではスタックオーバーフローします。次のレッスンの fib-dp ではループ版に書き換えてこの制約を回避します。
やってみよう
n = 30のとき、素朴版とメモ化版の実行時間を比べる。素朴版は数秒、メモ化版は一瞬で終わる。memoの中身をログ出力し、計算順序を確認する。fib(2)から順に埋まっていくのが見える。- メモ化を辞書ではなく配列
arr = [0] * (n+1)で書き直してみる。次レッスンalg-fib-dpに繋がる練習になる。
メモ化は「部分問題の解を覚える」という DP の本質を最もシンプルに体験できる形。配列版・ループ版へ進化させていけば、難しい DP も恐くなくなる。
よくある質問
Q. DP とメモ化再帰の違いは？
A. 本質的に同じです。メモ化再帰はトップダウンで自然に書け、DP テーブル（配列）はボトムアップで定数倍が速い傾向があります。複雑な状態遷移はメモ化、シンプルな漸化式は DP 配列が読みやすいことが多いです。
Q. DP の状態の数え方が分かりません
A. 「決めなければ次が決まらない情報」を全部状態にするのがコツです。例えばナップサックなら「現在の品物 i」と「残り容量 w」の 2 つで状態が決まります。状態が多くなりすぎたら DP は向かないかもしれません。
Q. メモリ最適化はどう考えますか？
A. DP テーブルが直前の行しか参照していなければ、2 行分（または 1 行 + 一時変数）で十分です。フィボナッチは 2 変数で済み、Edit Distance や LCS も 2 行 DP に圧縮できます。空間計算量を O(n^2) から O(n) や O(1) に減らせることが多いです。
次のレッスン
次は DP配列でフィボナッチ で、再帰で計算したフィボナッチ数列の途中結果をキャッシュし、指数関数的な計算量を線形に減らす「メモ化」の手法を学ぶ を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- メモ化フィボナッチ の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. メモ化フィボナッチ とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- fib(0) = 0、fib(1) = 1、それ以外は fib(k) = fib(k-1) + fib(k-2) を満たすこと
- メモ化を使い、各 k についての計算が 1 回で済むようにすること (計算量 O(n))
- n = 30 でも一瞬で結果が返ること (素朴再帰では数秒かかる)
入出力例
test-cases.txt
fibMemo(0) → 0
fibMemo(1) → 1
fibMemo(2) → 1
fibMemo(5) → 5
fibMemo(10) → 55
fibMemo(20) → 6765
fibMemo(30) → 832040