C#でトップダウン方式（メモ化）を用いてフィボナッチ数列を実装する方法

フィボナッチ数列は、0または1から始まり、その後に1が続き、以降の各数値（フィボナッチ数と呼ばれます）が「直前の2つの数値の合計」というルールに従って生成される数列です。

本記事で解説するトップダウン方式は、大きな問題をより小さく理解しやすい単位へ分割して解決していく手法です。フィボナッチ数列の計算においては、再帰呼び出しの結果を配列（メモ化テーブル）にキャッシュすることで、同じ計算を繰り返す無駄を省き、効率的に処理できます。

計算量について

• 時間計算量： O(N) — 各フィボナッチ数は一度だけ計算され、以降はメモ化された結果を参照するためです。
• 空間計算量： O(N) — 数値のサイズと同等の追加配列（メモ化用の配列）を作成するためです。

実装例

public class DynamicProgramming{
    public int fibonacciTopdownApproach(int n,int[] dpArr ){
        if(n==0 || n == 1){
            return n;
        }
        if(dpArr[n] != 0){
            return dpArr[n];
        }
        int res = fibonacciTopdownApproach(n - 1,dpArr) + fibonacciTopdownApproach(n - 2,dpArr);
        return dpArr[n] = res ;
    }
}

static void Main(string[] args){
    DynamicProgramming dp = new DynamicProgramming();
    int[] dpArr = new int[150];
    Console.WriteLine(dp.fibonacciTopdownApproach(12, dpArr));
}

コードのポイント

• ベースケースとして、nが0または1の場合はそのままnを返します。
• 配列dpArr[n]にすでに計算結果が格納されている場合（0以外の場合）は、再帰せずにその値を返します。これが「メモ化」による高速化の仕組みです。
• それ以外の場合は、n-1とn-2に対して再帰的に関数を呼び出し、その合計を配列に保存したうえで返します。

実行結果

144

このプログラムでは、12番目のフィボナッチ数である144が出力されます。素朴な再帰実装では指数時間O(2^N)かかるところを、トップダウン方式（メモ化）を採用することで線形時間O(N)まで大幅に改善できる点が、動的計画法の大きな利点です。