動的計画法part2(フィボナッチ数列)
問題概要
フィボナッチ数列の総和を返す
解法
1.メモ化
/* メモfb[]はあらかじめ-1(メモ無し)で初期化する */ fib(int a){ /* メモ化チェック */ if(fb[a] != -1 ) return fb[a]; if( a == 0 ) ret = 0; else if( a == 1 ) ret = 1; else ret = fib(a-1) + fib( a - 2 ) /* メモ格納 */ fb[a] = ret; return ret; }
2.動的計画法
漸化式作成
\[ fib[0] = 0 \]
\[ fib[1] = 1 \]
\[ fib[i] = fib[i-1] + fib[i-2] (i > 1) \]
漸化式より導きたいフィボナッチ数列の項数まで0から順に配列へ格納していく。
