参考：https://leetcode.cn/problems/climbing-stairs/solutions/286022/pa-lou-ti-by-leetcode-solution/
更详细的动态规划题解：https://leetcode.cn/problems/fibonacci-number/solutions/8330/dong-tai-gui-hua-tao-lu-xiang-jie-by-labuladong/
题目：
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
方法一：动态规划
斐波那契数的边界条件是 F(0)=0 和 F(1)=1。当 n>1 时，每一项的和都等于前两项的和，因此有如下递推关系：
F(n)=F(n−1)+F(n−2)
由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0) 和 F(1)。
根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 O(n) 的实现。由于 F(n) 只和 F(n−1) 与 F(n−2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)。
class Solution {
public:
int fib(int n) {
int a=0,b=1,c;
if(n<2)return n;
for(int i=2;i<=n;i++){
c=a+b;
a=b;b=c;
}
return c;
}
};
方法二：矩阵快速幂
还没弄懂
方法三：通项公式
斐波那契数 F(n)F(n)F(n) 是齐次线性递推，根据递推方程 F(n)=F(n−1)+F(n−2)，可以写出这样的特征方程：
求得\(x_1=\frac{1+\sqrt{5}}{2}\)，\(x_2=\frac{1-\sqrt{5}}{2}\)。设通解为\(F(n)=c_1x_1^n+c_2x_2^n\)，代入初始条件\(F(0)=0\)，\(F(1)=1\)，得\(c_1=\frac{1}{\sqrt{5}}\)，\(c_2=-\frac{1}{\sqrt{5}}\)。
因此斐波那契数的通项公式如下：
得到通项公式之后，就可以通过公式直接求解第 n 项。
class Solution {
public:
int fib(int n) {
double sqrt5 = sqrt(5);
double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
return round(fibN / sqrt5);
}
};
复杂度分析
代码中使用的 pow 函数的时空复杂度与 CPU 支持的指令集相关，这里不深入分析。
总结
这里形成的数列正好是斐波那契数列，答案要求的 f(n) 即是斐波那契数列的第 n 项（下标从 0 开始）。我们来总结一下斐波那契数列第 n 项的求解方法：
- n 比较小的时候，可以直接使用过递归法求解，不做任何记忆化操作，时间复杂度是 \(O(2^n)\)，存在很多冗余计算。
- 一般情况下，我们使用「记忆化搜索」或者「迭代」的方法，实现这个转移方程，时间复杂度和空间复杂度都可以做到 O(n)。
- 为了优化空间复杂度，我们可以不用保存 f(x−2) 之前的项，我们只用三个变量来维护 f(x)、f(x−1) 和 f(x−2)，你可以理解成是把「滚动数组思想」应用在了动态规划中，也可以理解成是一种递推，这样把空间复杂度优化到了 O(1)。
- 随着 nnn 的不断增大 O(n) 可能已经不能满足我们的需要了，我们可以用「矩阵快速幂」的方法把算法加速到 O(logn)。
- 我们也可以把 n 代入斐波那契数列的通项公式计算结果，但是如果我们用浮点数计算来实现，可能会产生精度误差。