LeetCode题解—斐波那契数列
前言
今天继续算法题：斐波那契数列
题目：斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0
F(1) = 1
F(N) = F(N - 1) + F(N - 2)
其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：输入：n = 2 输出：1
示例 2：输入：n = 5 输出：5
提示：0 <= n <= 100
解法一
斐波那契数列，面试中还是比较常遇到的，比较经典的一个题目。
题目意思很简单，F(N)的值为F(N - 1)与F(N - 2)之和，然后对于任意一个N，求结果。
首先想到的就是递归算法：
public static int fib(int n) {
if (n < 2)
return n;
return fib(n - 1) + fib(n - 2);
}因为要考虑到数字溢出问题，
★int 取值范围为Integer.MIN_VALUE(-2147483648) 到 Integer.MAX_VALUE（2147483647） ”
所以题目也说了，结果需要取模 1e9+7，所以修改代码：
public int fib(int n) {
if (n < 2)
return n;
int first = fib(n - 1) % 1000000007;
int second = fib(n - 2) % 1000000007;
return (first + second) % 1000000007;
}时间复杂度
每次是计算两个值，所以每次的计算数为2、4、8，有点像二叉树结构。
也就是时间复杂度为O(2^n)
空间复杂度
由于每次递归的时候都新建了变量，所以该解法的时间复杂度跟二叉树的空间复杂度一样，为树的深度，也就是O(n)
解法二
上述的递归算法是比较明晰的算法，但是有个问题，就是会出现大量的重复计算。
比如：f(5)=f(4)+f(3),f(4)=f(3)+f(2)
这里的f(3)就重复计算了，当整个递归算法完成的时候，就会出现大量的类似这种的重复计算。
所以我们可以优化下，把重复的数字存储起来：
public int fib3(int n) {
return fib3(n, new HashMap());
}
public int fib3(int n, Map<Integer, Integer> map) {
if (n < 2)
return n;
if (map.containsKey(n))
return map.get(n);
int first = fib3(n - 1, map) % 1000000007;
map.put(n - 1, first);
int second = fib3(n - 2, map) % 1000000007;
map.put(n - 2, second);
int res = (first + second) % 1000000007;
map.put(n, res);
return res;
}把每个计算后的值都存储到Map中，然后每次计算的时候如果Map中已经有对应的值就直接用，否则就按照之前的逻辑进行前两个数相加。
时间复杂度
该解法中，不会再有重复计算，所以实际上只计算了每个f(n)的值，从0——n。所以时间复杂度为O(n)
空间复杂度
由于用到了单独的Map集合，以及递归过程中新建的变量，所以空间复杂度为O(2n),也就是O(n)
解法三
当然，上述算法还不是最优解法，空间复杂度太高，要用到单独的Map。
那么最优解法是什么呢？
动态规划。
★动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。 ”
简单的说就是分成多个阶段，下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。
在我们这次的题目中，每个值都依赖于前面两个值的计算，如果这两个值设置为变量a和b，那么每次计算完，都可以对a和b重新赋值，然后相加，一直这样操作下去～
不知道你们明白没有呢？看看源码吧：
public int fib(int n) {
int a = 0, b = 1, sum=0;
if(n==0)return 0;
if(n==1)return 1;
for (int i = 2; i < n+1; i++) {
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return sum;
}从f(0)+f(1)开始，每次计算完和后，再将两个变量赋值为之前计算好的值，来进入下一个阶段。
这段代码还可以再进行简化：
public static int fib2(int n) {
int a = 0, b = 1, sum;
for (int i = 0; i < n; i++) {
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return a;
}这里有个小细节，结果输出用到了a，而不是sun。这是为啥呢？
这主要是考虑到三种不同情况（n=0，n=1，n>=2），正常情况下要针对这三种情况单独返回，也就是刚才的解法，但是为了写的更简便，就直接融合了这几种特殊情况：
n=0的时候，不进入循环，直接返回a的值也就是0。n=1的时候，按道理来不用进入循环，直接返回b值1，跟上述的a冲突了。所以选择进入循环一次，给a赋值了b的值，然后返回a，也就是1。n=2的时候，循环了两次，但是实际我们只需要取第一次循环的和值，所以要返回a。
时间复杂度
循环n次，所以时间复杂度为O(n)
空间复杂度
只用到几个临时变量，所以空间复杂度为O(1)
参考
https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/