C#でボトムアップアプローチを使ってフィボナッチ数列を実装する方法

フィボナッチ数列は、0または1から始まり、その後に1が続き、「各数値（フィボナッチ数）は直前の2つの数値の合計に等しい」という規則に従って進んでいく一連の数列です。具体的には、0, 1, 1, 2, 3, 5, 8, 13, 21, 34… のように数列が展開されます。

ボトムアップ（Bottom-up）アプローチとは、動的計画法（Dynamic Programming）における代表的な手法の一つです。このアプローチでは、まず最も基本的な小さな部分問題から解決していき、それらを段階的に統合しながら、最終的に全体の完全な解を導き出します。フィボナッチ数列の場合、dpArr[1] = 1 という初期値から出発し、forループによって小さい順に各フィボナッチ数を配列へ格納していくことで、再帰呼び出しによる重複計算を避け、効率的に求めることができます。

計算量

• 時間計算量： O(N)
• 空間計算量： O(N)

数値を一度ずつ計算して配列に保存するため、処理時間は入力サイズNに対して線形に増加します。また、結果を保存するためにサイズNの配列が必要となるため、空間計算量もO(N)となります。

実装例

public class DynamicProgramming{
    public int fibonacciBottomupApproach(int n){
        int[] dpArr = new int[150];
        dpArr[1] = 1;
        for (int i = 2; i <= n; i++){
            dpArr[i] = dpArr[i - 1] + dpArr[i - 2];
        }
        return dpArr[n];
    }
}

static void Main(string[] args){
    DynamicProgramming dp = new DynamicProgramming();
    Console.WriteLine(dp.fibonacciBottomupApproach(5));
}

コードの解説

このコードでは、あらかじめサイズ150のint型配列 dpArr を用意し、初期条件として dpArr[1] に 1 を設定しています。その後、i = 2 から n までループを回し、「直前の2つの要素の合計」を順次格納していきます。すべての計算が完了した時点で、dpArr[n] を返すことで n 番目のフィボナッチ数が得られます。

出力

5

n = 5 を指定した場合、フィボナッチ数列は 0, 1, 1, 2, 3, 5 と続くため、5番目のフィボナッチ数である「5」が出力されます。