题目的主要信息：

• 一只青蛙一次可以跳上1级台阶，也可以跳上2级，先后次序算不同的方案
• 求该青蛙跳上一个n级的台阶总共有多少种跳法
• 要求：时间复杂度$O(n)O(n)$，空间复杂度$O(1)O(1)$

方法一：动态规划

具体做法：

我们用可以考虑第n级台阶，它可以由第n-1级台阶跳1级而来，也可以由第n-2级台阶跳2级而来，那么第n级台阶的方案就是第n-1级的方案数加上第n-2级的方案。不断往前推，每个台阶的方案数都可以由前两个台阶相加得到，这就是得到了斐波那契数列的递推公式：$f(n)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)$ 那我们可以用dp数组动态规划不断相加得到。

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数组，空间复杂度为$O(n)O(n)$，不满足要求，因此我们对空间优化一下：注意到每次循环只使用到了第$i-1i-1$个变量和第$i-2i-2$个变量，那我们可以用两个变量不断滚动来优化。

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;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一次遍历
• 空间复杂度：$O(1)O(1)$，常数级遍历

方法二：矩阵快速幂

具体做法：

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

这样我们只要求得基础矩阵的n-2次方与最初的几个元素相乘，取矩阵第一个元素就是我们要求的F(n)。而矩阵的次方，我们可以采用矩阵快速幂，参考这篇文章。对于一个矩阵我们可以用如下的方式计算，缩短时间： 比如我们得到它的2次方，后续的2次方就不用再计算了，我们得到4次方后续的也不用计算了，这样计算时间可以缩短到$O(lo{g}_{2}n)O(log\_2n)$.

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)
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，计算了矩阵的$n-2n-2$次方，因为使用了矩阵快速幂，缩短到$O(lo{g}_{2}n)O(log\_2n)$
• 空间复杂度：$O(1)O(1)$，所有的矩阵变量都是常数级的

方法三：公式计算

具体做法：

斐波那契数列除了递推公式，还有数学公式：

需要注意的是这个公式其实$F(0)=0F(0)=0$、$F(1)=1F(1)=1$，因此我们排除前两种情况后要对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));; //公式
    }
};

当然上述公式还可以用快速幂来优化，如果我们要计算$5^{10}5^\{10\}$，常规的算法是$5\ast 5=255*5=25$，然后再$25\ast 5=12525*5=125$，如此往下，一共是$99$次运算，即$n-1n-1$次。但是我们可以考虑这样：$5\ast 5=255*5=25$(二次）、$25\ast 25=62525*25=625$（四次）、$625\ast 625=\mathrm{.}\mathrm{.}\mathrm{.}625*625=...$（八次），这是一个二分的思维，运算次数缩减到了$lo{g}_{2}nlog\_2n$次，公式如下:

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));; //公式
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，Pow函数使用了快速幂缩短了计算时间
• 空间复杂度：$O(1)O(1)$，常数级变量