題目描述

斐波那契數，通常用 F(n) 表示，形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
給你 n ，請計算 F(n) 。

示例

示例 1：
輸入：2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：
輸入：3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2

方法一：遞推求解

class Solution {
public:int fib(int n) {vector<int> f(31);f[0]=0;f[1]=1;for(int i=2;i<=n;i++) f[i]=f[i-1]+f[i-2];return f[n];}
};

斐波那契0.618，復雜度分析：

• 時間復雜度：O(n)，進行了一個循環
• 空間復雜度：O(n)，創建了一個n大小的數組
  

方法二：遞歸求解

class Solution {
public:int fib(int n) {if(n==0) return 0;if(n==1) return 1;return fib(n-1)+fib(n-2);}
};

復雜度分析：

• 時間復雜度：O(2^n)，遞歸求解，時間長，如果n稍微大點就會超時了。
• 空間復雜度：O(n),經過n次壓棧。