「这是我参与2022首次更文挑战的第12天，活动详情查看：2022首次更文挑战」。
斐波那契数列想必大家都听过，如果感觉斐波那契数列有点陌生的同学，肯定是没有好好学算法。一般在讲解递归的时候，我们都会拿出斐波那契数列这个例子来，因为它实在太经典了，今天我们就来深入研究一下斐波那契数列的解法。
什么是斐波那契数列？
数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。他当时是这样提出的：假设一对刚出生的小兔一个月后就能长成大兔，再过一个月就能生下一对小兔，并且此后每个月都生一对小兔，一年内没有发生死亡，问：一对刚出生的兔子，一年内繁殖成多少对兔子?
形成数列就是：0、1、1、2、3、5、8、13、21、34、……
在数学上，斐波那契数列以如下被以递推的方法定义：F( 0 )=0，F( 1 )=1, F( n )=F( n - 1 ) + F( n - 2 )（n ≥ 2，n ∈ N*）
解法一：递归
时间复杂度：O(2ⁿ)
空间复杂度：O(1)
斐波那契数列就是为递归而生的，我们从题中就可以找到它的规律就是后一个数是前两个数之和，它的边界就是F( 0 )=0，F( 1 )=1，它的递归调用就是 F( n - 1 ) + F( n - 2 ) 。
原理图：
代码如下：
public int fibonacci(int n) {
if (n < 2) {
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}
解法二：记忆化搜索（备忘录算法）
时间复杂度：O(n)
空间复杂度：O(n)
通过上边递归的原理图片可以看出，递归时大量的中间数据是存在重复计算的，我们将这些重复的中间值通过Map缓存起来，这样同样的值我们只需要递归计算一次，就能得到解，能够极大的提高递归的效率，这就是记忆化搜索。
此种算法，是典型的用空间换时间，有n个数我们就需要缓存n个值。
优化后我们需要的计算量，是不是大幅提升呢，从下图就可以得到答案
代码如下：
public int fibonacci(int n, Map<Integer,Integer> cache) {
if (n < 2) {
return n;
}
if (cache.containsKey(n)) {
return cache.get(n);
}
int value = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
cache.put(n,value);
return value;
}
解法三：动态规划
时间复杂度：O(n)
空间复杂度：O(1)
递归是一种自顶向下求解的过程，那么我们能不能自低向上求解呢？
自低向上就是说我们由F( 0 )=0，F( 1 )=1，F( 2 )...F( n )这样是不是更好呢？很显然可以的。
正是由于斐波那契数存在这种递推关系，所以我们可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0) 和 F(1)。
根据动态规划的状态转移方程和边界条件，我们可以得到时间复杂度和空间复杂度都是 O(n) 的实现。由于 F(n) 只和 F(n−1) 与 F(n−2) 有关，因此可以使用 【滚动数组思想】 把空间复杂度优化成 O(1)。
代码如下：
public int fibonacci(int n) {
if (n < 2) {
return n;
}
int p = 0, q = 0, r = 1;
for (int i = 2; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}
解法四：矩阵快速幂
时间复杂度：O(logn)
空间复杂度：O(1)
动态规划的时间复杂度是 O(n)。我们可以使用矩阵快速幂的方法来降低时间复杂度。
首先构建递推关系：
得到
令
public int fibonacci(int n) {
if (n < 2) {
return n;
}
int[][] q = {{1, 1}, {1, 0}};
int[][] res = pow(q, n - 1);
return res[0][0];
}
public int[][] pow(int[][] a, int n) {
int[][] ret = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
public int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
解法五：通项公式
斐波那契数 F(n) 是齐次线性递推，根据递推方程 F(n)=F(n-1)+F(n-2)，
可以写出这样的特征方程：x²=x+1
代码中pow 函数的时间、空间复杂度与 CPU 支持的指令集相关，这里不深入分析。
代码如下：
public int fibonacci(int n) {
double sqrt5 = Math.sqrt(5);
double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
return (int) Math.round(fibN / sqrt5);
}
说明：
解法四，解法五是在LeetCode题解中上发现的，效率是真的高，但我看的也是模棱两可，这些都是高等数学的相关知识点，感兴趣的可以深入研究一下，算法的尽头还是数学啊！！！
前三个解法是我们每个人都应该掌握的。
