メモ化再帰方法によるフィボナッチ数列

メモ化再帰方法によるフィボナッチ数列をALDS_1_10_A:BibonacciNumberを例題に学びます

メモ化再帰方法とは

複雑な計算処理の結果を保存しておき、再度その計算が必要な際にその値を使うことで
処理の負担を減らすことです。

問題からフィボナッチ数列の計算方法を抜粋すると

             1 (n = 0)
fib(n)= 1 (n = 1)
              fib(n - 1) + fib(n- 2)

となりますが、この計算結果を配列などに保存しておき、
再帰的に計算する際に保存した計算結果を使うことで、
計算にかかる処理を短縮します。

では、ALDS_1_10_A:BibonacciNumberに合わせた全体のプログラムです。

#include <iostream>
using namespace std;

int result[45];

int fib(int n){
    if(n == 0 || n == 1)return result[n] = 1;
    if(result[n] != -1) return result[n];
    return result[n] = fib(n - 1) + fib(n - 2);
}

int main(){
    int n;
    for(int i = 0;i < 45;++i){
        result[i] = -1;
    }
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}