509. 斐波那契数
知识点：递归；动态规划
题目描述
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
示例
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
解法一：递归
这道题目可以说是大部分人的递归入门题，是一道很好的样题，之所以入门是因为题目中将结束条件和等式关系给出来了。所以比较简单。
class Solution {
public int fib(int n) {
if(n < 2) return n;
return fib(n-1)+fib(n-2);
}
}
递归算法的时间复杂度怎么计算呢，其实就是子问题个数乘以解决一个子问题需要的时间。子问题个数就是递归树中的节点总数，二叉树的节点子树是2^n, 一个子问题需要的时间，在单层里没有循环，只有加法操作，所以为1，所以整体的复杂度就是O(2^N);指数级别；
为什么会是指数级别，原因就在于有太多的重复计算。
首先要计算f20，递归调用f19，f19去调用f18，这样直到f1，然后最后一颗子树调f2，再逐层返回，最后得到f19，然后要调用f18，f18去调用f17，f17去调用f16，... ， 但是我们在算f19的时候已经都算出来了啊，什么f18，f17都有了，就像图里有的，难道还要再算一遍？递归可是耗费巨大啊，其实这就是重叠子问题！
所以我们可以用一个备忘录(dp数组)把已经好不容易算出来的结果存起来，那再算的时候如果有，就直接用就可以了。其实这就引出了动态规划，只不过我们的动规不像递归那样自顶向下(要算f20先去算f19，直至f1)，动规是自底向上，由f1得到f2，得到f3直至得到f20，所以动规脱离了递归，用for循环的迭代。
解法二：动态规划
动态规划的典型类型：
背包问题；
打家劫舍；
股票问题；
子序列问题；
动态规划常常用于求解多阶段决策问题
动态规划问题的问法：只问最优解(常和最值联系在一起)，不问具体的解；
我们先创建dp数组，首先
- 1.确定dp数组和其下标的含义；(第i个索引的斐波那契值)
- 2.确定递推公式，即状态转移方程；(题目中给出，fn=fn-1+fn-2)
- 3.dp初始化；base case; (题目中给出了)
class Solution {
public int fib(int n) {
int[] dp = new int[n+1]; //第i个索引的函数值为dp[i];
if(n <= 1) return n;
dp[0] = 0; //base case;
dp[1] = 1;
for(int i = 2; i < n+1; i++){
dp[i] = dp[i-1]+dp[i-2]; //递推公式：状态转移方程；
}
return dp[n];
}
}
时间复杂度：O(N);
其实还可以进行优化，因为我们任一状态都只和前两个状态有关，所以不用维持一个这么长的数组，只需要三个变量就可以了。
class Solution {
public int fib(int n) {
if(n <= 1) return n;
int pre = 0, cur = 1; //维持两个状态；
for(int i = 2; i < n+1; i++){
int sum = pre+cur;
pre = cur;
cur = sum; //状态转移
}
return cur;
}
}