题解 | #斐波那契数列#

方法①：该方法最简单，但是时间复杂度为O（2^n）

     int Fibonacci(int n) {
         if(n == 0)
             return 0 ;
         else if(n <= 2)
                 return 1;
         else
             return Fibonacci(n-1)+Fibonacci(n-2);
     }

方法②：该方法为DP，时间复杂度为O（n）

   int Fibonacci(int N) {
        if(N == 0 ) return 0;
        if(N == 1 || NZERO == 2) return 1;
        vector<int> dp(N+1,0);
        //base case
        dp[1] = dp[2] = 1;
        for(int i = 3 ; i <= N ; ++i)
             dp[i] = dp[i - 1] + dp[i - 2];
         return dp[N];
     }

方法③：该方法为DP的升级版，时间复杂度为O（n）

     int Fibonacci(int n) {
         int a = 1;
         int b = 0;
         int ret = 0;
         if(n == 0) return 0;
         if(n == 1) return 1;
         for (int i = 0 ; i < n-1 ; i++)
         {
             ret = a + b;
             b = a;
             a = ret;
         }
         return ret;
     }