#include <bits/stdc++.h>
using namespace std;
const maxn=1000;
int fibonacci(int n) //f0=1 f1=1 f2=2 f3=3 f4=5.....
{
       if(n==0||n==1)
              return 1;
       else
          return fibonacci(n-1)+fibonacci(n-2);

}
int dp[maxn];
int f(int n)//动态规划版本
{
     if(n==0||n==1)
              return 1;
     if(dp[n]!=0)//说明已经计算过
       return dp[n];
     else
     {
       dp[n]=f(n-1)+f(n-2);
       return dp[n];
     }

}
int main()
{
     memset(dp,0,sizeof(dp));
      cout<<fibonacci(1000000);
      cout<<f(10000000); //复杂度从2的n次方降低到n

    return 0;
}