DP配列でフィボナッチ
DP配列でフィボナッチ
このレッスンで分かること
- 動的計画法では、トップダウン (再帰 + メモ) とボトムアップ (ループ + 配列) のどちらでも書けるのが普通です
- 方向性の違いは図にすると分かりやすいです
- 図のポイント (テキスト併記)
DP配列でフィボナッチ とは
再帰を使わず、配列とループでフィボナッチ数を計算する「ボトムアップ DP」を学ぶ。スタックを使わないので大きな n でも安全。
前回のレッスンでは メモ化 を使って fib(n) を O(n) まで高速化しました。これは「トップダウン DP」と呼ばれる手法で、fib(n) から始めて必要な部分問題を再帰的に展開しながら解いていきます。今回はそれを裏返した ボトムアップ DP に挑戦します。fib(0) から順番に 配列を埋めていく スタイルです。
動的計画法では、トップダウン (再帰 + メモ) とボトムアップ (ループ + 配列) のどちらでも書けるのが普通です。それぞれに長所と短所があり、状況に応じて選び分けます。今回はフィボナッチを題材に、ボトムアップの書き方を体に叩き込みます。
ボトムアップ DP は「小さい問題から順に答えを表に書き込む」イメージ。スタックを使わないので大きな n でも安全。
ボトムアップとトップダウンの違い
方向性の違いは図にすると分かりやすいです。
図のポイント (テキスト併記)
- ボトムアップでは矢印の向きに沿って 左から右に表を埋めて いきます
ボトムアップでは矢印の向きに沿って 左から右に表を埋めて いきます。fib(0)、fib(1) という基底ケースを最初に書き込み、あとは dp[k] = dp[k-1] + dp[k-2] の漸化式に従って 1 マスずつ前進するだけです。再帰関数を呼ばないので スタックオーバーフローの心配がありません。
再帰版は関数呼び出しのコストがあるが、ループ版はメモリアクセスのみ。同じ
O(n)でも実測は数倍速いことが多い。
配列を使わない最適化
よく見ると、dp[k] を計算するのに必要なのは直前 2 要素 dp[k-1] と dp[k-2] だけです。配列を n+1 要素も用意するのはムダなので、変数 2 つ に圧縮できます。これでメモリ使用量は O(n) から O(1) に落ちます。動的計画法 の常套手段なので覚えておきましょう。
Python での実装 (配列版)
Python
def fibDp(n):
if n < 2:
return n
dp = [0] * (n + 1)
dp[0], dp[1] = 0, 1
for k in range(2, n + 1):
dp[k] = dp[k - 1] + dp[k - 2]
return dp[n]まず n < 2 の基底ケースを処理してから、サイズ n+1 の dp 配列を作ります。for ループは 2 から n まで回し、漸化式どおりに埋めていくだけ。再帰の影も形もなく、シンプルです。
Python での実装 (変数 2 つに圧縮)
Python
def fibDp(n):
if n < 2:
return n
a, b = 0, 1
for _ in range(n - 1):
a, b = b, a + b
return b変数 2 つ版は 配列 を持たないので、n = 10^6 のような巨大入力でもメモリを気にせず処理できます。ただし可読性は配列版の方が高いので、最初は配列版から書くのがおすすめです。
JavaScript での実装
JavaScript
function fibDp(n) {
if (n < 2) return n;
const dp = new Array(n + 1).fill(0);
dp[0] = 0;
dp[1] = 1;
for (let k = 2; k <= n; k++) {
dp[k] = dp[k - 1] + dp[k - 2];
}
return dp[n];
}JavaScript も配列を初期化してから for ループで埋めるだけ。new Array(n + 1).fill(0) の書き方を覚えておくと便利です。Array(n).fill(0) だけだと dp[n] にアクセスしたとき undefined になるので、n + 1 要素確保するのを忘れないようにしましょう。
トップダウンとボトムアップの選び方
どちらを使うかは状況次第ですが、おおまかな指針は次の通りです。再帰の自然さ を活かしたいときや、部分問題が疎 (全部の状態を計算しなくて済む) のときは トップダウン が向きます。逆に 状態数が密 で全部埋めることが分かっているなら、関数呼び出しのオーバーヘッド がないぶん ボトムアップ が高速です。さらに、配列を圧縮 できるかどうかも見極めポイントで、フィボナッチや階段問題のような 直前数項にしか依存しない 漸化式は変数だけで済みます。
競プロでは「困ったらボトムアップ」が無難。状態を整理しやすく、デバッグもしやすい。
よくある間違い
1 つ目は 配列サイズが足りない。n+1 要素必要なところを n で確保するとインデックスエラーになります。2 つ目は 基底ケースの順序。dp[0] = 0 と dp[1] = 1 を入れる前にループに突入してしまうと、すべて 0 になります。3 つ目は n = 0 や n = 1 の特例。配列のサイズが小さすぎてエラーになりがちなので、最初の if n < 2: return n で逃がしておくのが定石です。
やってみよう
n = 50を素朴な再帰、メモ化、配列 DP、変数 2 つ版の 4 通りで計算し、実行時間を比較する。- 配列の中身を出力して、
fib(0) = 0から順に埋まる様子を確認する。 - 変数 2 つ版を題材に、
fib(n) mod 1000000007を計算する関数に拡張する。競プロでよく出てくるパターン。
ボトムアップ 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 に圧縮できます。フィボナッチのように直前数項にしか依存しない DP は O(n) から O(1) へ、LCS や Edit Distance のような 2 次元 DP は O(nm) から O(n)（2 行 DP）へ削減できます。
次のレッスン
次は 階段の登り方 で、再帰を使わず、配列とループでフィボナッチ数を計算する「ボトムアップ DP」を学ぶ を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- DPでフィボナッチ の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. DPでフィボナッチ とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 再帰呼び出しを使わず、ループで実装すること
- fib(0) = 0、fib(1) = 1 から始め、fib(k) = fib(k-1) + fib(k-2) で配列を埋めること
- n = 40 でも一瞬で結果が返ること (O(n) 時間)
入出力例
test-cases.txt
fibDp(0) → 0
fibDp(1) → 1
fibDp(2) → 1
fibDp(7) → 13
fibDp(15) → 610
fibDp(25) → 75025
fibDp(40) → 102334155