C++で動的計画法を用いてフィボナッチ数を求めるプログラム

フィボナッチ数列は、次のような数列です。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,……

この数列では、第n項は「第(n-1)項」と「第(n-2)項」の和として定義されます。

数列を生成する方法としては再帰的なアプローチも考えられますが、素朴な再帰では同じ計算を何度も繰り返すため非効率です。一方、動的計画法を用いれば、計算済みのフィボナッチ数をすべてテーブル（配列）に保存し、その結果を再利用することで、次々と新しい項を効率よく求められます。

入力 − 求めたい項の番号を入力として受け取ります。ここでは例として10を入力します。

出力 − 第10項のフィボナッチ数は 55 となります。

アルゴリズム

genFiboSeries(n)

入力： 求める最大項数 n

出力： 第n項のフィボナッチ数

開始
サイズ n+2 の配列 fibo を定義する
fibo[0] := 0
fibo[1] := 1
i が 2 から n になるまで繰り返す
    fibo[i] := fibo[i-1] + fibo[i-2]
繰り返し終了
fibo[n] を返す
終了

サンプルコード

#include<iostream>
using namespace std;
int genFibonacci(int n) {
    int fibo[n+2]; // フィボナッチ数を格納する配列
    // 数列の0番目と1番目はそれぞれ0と1
    fibo[0] = 0;
    fibo[1] = 1;
    for (int i = 2; i <= n; i++) {
        // 直前の2項を使って第i項を生成
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    return fibo[n];
}
int main () {
    int n;
    cout << "Enter number of terms: "; cin >> n;
    cout << n << " th Fibonacci Terms: " << genFibonacci(n) << endl;
}

実行結果

Enter number of terms: 10
10th Fibonacci Terms: 55

計算量について

この動的計画法によるアプローチでは、各項を一度だけ計算して配列に保存するため、時間計算量は O(n)、空間計算量も O(n) となります。一方、メモ化を行わない素朴な再帰では指数時間 O(2ⁿ) かかるため、n が大きくなるほど動的計画法の優位性が顕著になります。さらに、直前の2項だけを保持する変数を使えば、空間計算量を O(1) まで削減することも可能です。