题目
斐波那契数，通常用 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.
示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
- 0 ≤ N ≤ 30
分析与题解
斐波那契数列数列的求取公式本质上就是动态规划的状态转移方程。此题目不考虑运行时间的问题，所以解法比较多。
暴力递归
直接套用斐波那契数列的递归公式进行结题，对于该递归问题，作出递归树可以帮助我们进行理解：
这个递归树怎么理解？就是说想要计算原问题f(20)，我就得先计算出子问题f(19)和f(18)，然后要计算f(19)，我就要先算出子问题f(18)和f(17)，以此类推。最后遇到f(1)或者f(2)的时候，结果已知，就能直接返回结果，递归树不再向下生长了。
代码如下：
class Solution {
public:
int fib(int n) {
if(n==1)
return 1;
if(n==0)
return 0;
return fib(n-1)+fib(n-2);
}
};
但该递归算法中，算法的时间复杂度为O(2^n)。原因在于存在大量的重复计算，比如f(18)被计算了两次，并且以f（18）为根结点的递归树的体量巨大，会耗费巨大的时间。
记录状态的递归解法
既然耗时的原因是重复计算，我们可以自定义一个备忘录，在递归计算子问题的答案时，在返回前先在备忘录中进行记录，具体策略如下：
- 0为初始值，代表之前仍未得出子问题的答案
- 非0值表示子问题之前已经计算过，并且实际值即为计算结果
一般数组vector作为备忘录，当然使用哈希表也是可以接受的。代码如下：
class Solution {
public:
int helper(vector<int>& table, int n){
if(n==0)
return 0;
if(n==1)
return 1;
if(table[n]!=0)
return table[n];
else return helper(table,n-1)+helper(table,n-2);
}
int fib(int n) {
//初始化一个n+1位的数组，值全部初始化为0
//作为重复结点的状态记录册
vector<int> table(n+1,0);
return helper(table, n);
}
};
“备忘录”自底向上遍历
之前的想法都是自底向上进行递归，只不过使用备忘录优化了子问题重复计算的问题。我们可以延续备忘录的想法，尝试自递归问题的终止点向上反向推导：
注意题设条件中特殊值单独讨论，代码如下：
class Solution {
public:
int fib(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
vector<int> table(n+1,0);
table[1]=table[2]=1;
for(int i=3;i<=n;i++){
table[i]=table[i-1]+table[i-2];
}
return table[n];
}
};
自底向上“优化版”
在上一版中，我们对于求取斐波那契数列第n个数的问题，创建了一个容量为n+1的动态数组。但仔细品斐波那契数列，也就是状态转移方程后，可以发现：其实求值我们只需要更新当前结点前相邻的两个数值即可。
代码可以放弃使用vector，精简为：
class Solution {
public:
int fib(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
int prev1 = 0;
int prev2 = 1;
int ans = 0;
for(int i=2;i<=n;i++){
ans = prev1 + prev2;
prev1 = prev2;
prev2 = ans;
}
return ans;
}
};