動的計画法を使用してフィボナッチ数を見つけるC++プログラム

フィボナッチ数列は次のようになります

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,……

このシーケンスでは、n番目の項は（n-1） ^th の合計です。 および（n-2） ^th 用語。

生成するには再帰的アプローチを使用できますが、動的計画法では手順が簡単です。すべてのフィボナッチ数をテーブルに格納できます。そのテーブルを使用することで、このシーケンスの次の項を簡単に生成できます。

入力 −用語番号を入力として使用します。 10だと言う

出力 −10番目の fibinacciの用語は55です

アルゴリズム

genFiboSeries（n）

入力

用語の最大数。

出力

n番目のフィボナッチ用語。

Begin
define array named fibo of size n+2
fibo[0] := 0
fibo[1] := 1
for i := 2 to n, do
fibo[i] := fibo[i-1] + fibo[i-2]
done
return fibo[n]
End

サンプルコード

#include<iostream>
using namespace std;
int genFibonacci(int n) {
   int fibo[n+2]; //array to store fibonacci values
   // 0th and 1st number of the series are 0 and 1
   fibo[0] = 0;
   fibo[1] = 1;
   for (int i = 2; i <= n; i++) {
      fibo[i] = fibo[i-1] + fibo[i-2]; //generate ith term using previous
      two terms
   }
   return fibo[n];
}
int main () {
   int n;
   cout << "Enter number of terms: "; cin >>n;
   cout << n<<" th Fibonacci Terms: "<<genFibonacci(n)<<endl;
}

出力

Enter number of terms: 10
10th Fibonacci Terms: 55