読者です 読者をやめる 読者になる 読者になる

動的計画法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から順に配列へ格納していく。