算法分享之斐波那契数列的高级解法

斐波那契数列数列，我们都知道，是一个非常简单的问题，最初由数学家斐波那契根据兔子的问题提出来，递推公式为，常规解法如果要求可以使用递归，不断计算子问题相加，但是这样其实是一个树型递归，会重复计算很多内容，因此很浪费时间，接下来我要介绍几种至多是复杂度的算法解决斐波那契数列问题。

斐波那契数列问题可以参考牛客网的跳台阶 、斐波那契数列 、不死神兔问题等问题。

我们这里讨论且的情况，具体可以参考这篇题解 。

方法一：动态规划/迭代

对于递推公式可以用一个数组记录每位的函数值，然后初始化前两位，后续不断由前面两个相加即可得到。

class Solution {
public:
    int jumpFloor(int n) {
        if (n <= 1)    //从0开始，第0项是1，第一项是1
             return n;
        vector<int> dp(n + 1); 
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2]; //公式不断相加
        return dp[n];
    }
};

但是这个方法使用了dp数组，空间复杂度为，还可以对空间优化一下：注意到每次循环只使用到了第个变量和第个变量，那我们可以用两个变量不断滚动来优化。

class Solution {
public:
    int jumpFloor(int n) {
        if (n <= 1)    //从0开始，第0项是1，第一项是1
             return n;
        int dpi_2 = 1; //初始化第0级
        int dpi_1 = 1; //初始化第1级
        int res = 0;
        for(int i = 2; i <= n; i++){
            res = dpi_1 + dpi_2; //公式相加
            dpi_2 = dpi_1; //变量更新
            dpi_1 = res;
        }
        return res;
    }
};

方法二：矩阵快速幂

对于斐波那契数列，我们可以有如下的推导：

这样我们只要求得基础矩阵的n-2次方与最初的几个元素相乘，取矩阵第一个元素就是我们要求的。而矩阵的次方，我们可以采用矩阵快速幂，参考这篇文章。对于一个矩阵我们可以用如下的方式计算，缩短时间：

比如我们得到它的2次方，后续的2次方就不用再计算了，我们得到4次方后续的也不用计算了，这样计算时间可以缩短到.

class Solution {
public:
    vector<vector<int>> base = { //基础矩阵
        {1, 1},
        {1, 0}
    };
    vector<vector<int>> Mul(vector<vector<int>>& x, vector<vector<int>>& y){ //x矩阵乘上y矩阵
        vector<vector<int>> res(2, vector<int>(2, 0));
        for(int i = 0; i < 2; i++){ //遍历相乘相加
            for(int j = 0; j < 2; j++){
                for(int k = 0; k < 2; k++){
                    res[i][j] = (res[i][j] + x[i][k] * y[k][j]);
                }
            }
        }
        return res;
    }
    vector<vector<int>> Pow(vector<vector<int>>& x, int k){ //矩阵快速幂
        vector<vector<int>> res(2, vector<int>(2, 0));
        for(int i = 0; i < 2; i++)
            res[i][i] = 1; //初始化为单位矩阵
        while(k){
            if(k & 1)
                res = Mul(res, base);
            k = k >> 1;
            base = Mul(base, base);
        }
        return res;
    }
    int jumpFloor(int n) {
        if(n <= 1)  //从0开始，第0项是1，第一项是1
            return n; 
        vector<vector<int> > a = base; 
        vector<vector<int> > b = {{2, 1}, {1, 1}}; //F(2) F(1) F(1) F(0)
        vector<vector<int> > c = Pow(a, n - 2); //基础矩阵的n-2次方
        return Mul(c, b)[0][0]; //F(n)
    }
};

方法三：公式计算

斐波那契数列除了递推公式，还有直接的数学表达式：

需要注意的是这个公式其实、，因此我们排除前两种情况后要对n添加1.

class Solution {
public:
    int jumpFloor(int n) {
        if(n <= 1)  //从0开始，第0项是1，第一项是1
            return n;
        n = n + 1; //迎合公式
        return (sqrt(5) / 5) * (pow((1 + sqrt(5)) / 2, n) - pow((1 - sqrt(5)) / 2, n));; //公式
    }
};

当然上述公式还可以用快速幂来优化，如果我们要计算，常规的算法是，然后再，如此往下，一共是次运算，即次。但是我们可以考虑这样：(二次）、（四次）、（八次），这是一个二分的思维，运算次数缩减到了次，公式如下:

class Solution {
public:
    double Pow(double x, int y){ //快速幂
        double res = 1;
        while(y){
            if(y & 1) //可以再往上乘一个
                res = res * x;
            x = x * x; //叠加
            y = y >> 1; //减少乘次数
        }
        return res;
    }
    int jumpFloor(int n) {
        if(n <= 1)  //从0开始，第0项是1，第一项是1
            return n;
        n = n + 1; //迎合公式
        return (sqrt(5) / 5) * (Pow((1 + sqrt(5)) / 2, n) - Pow((1 - sqrt(5)) / 2, n));; //公式
    }
};