题目的主要信息：

对于n阶台阶，青蛙每次可以选择跳1到n中任意一个数的阶梯数
n为正整数，求青蛙跳上n级台阶的方案数

方法一：暴力解法

具体做法：

对于n个阶梯，如果青蛙第一次选择跳1阶，那么它有还剩下n-1阶，如果选择跳2阶，那么它还剩下n-2阶以此类推，后面剩下的都是子问题，则数学化公式即为： $f (n) = f (n - 1) + f (n - 2) + . . . + f (n - (n - 1)) + f (n - n)$ 我们可以用一个辅助数组依次保存0-n的跳法数，每个数都按照上述公式，遍历数组计算即可。

class Solution {
public:
    int jumpFloorII(int number) {
        vector<int> dp(number + 1, 0); //记录i阶的跳法
        dp[0] = 1; //初始化
        dp[1] = 1;
        for(int i = 2; i <= number; i++)
            for(int j = 1; j <= i; j++) 
                dp[i] += dp[i - j];  //公式
        return dp[number];
    }
};

复杂度分析：

时间复杂度： $O (n^{2})$ ，两层循环
空间复杂度： $O (n)$ ，辅助数组dp

方法二：递归

具体做法：

方法一的公式，我们将其改写： $f (n) = f (n - 1) + f (n - 2) + . . . + f (n - (n - 1)) + f (n - n) = f (0) + f (1) + f (2) + . . . + f (n - 1)$ 因此，可以递归地计算其子问题，然后依次相加即可。图片说明

class Solution {
public:
    int jumpFloorII(int number) {
        if(number <= 1) //1或0都是1
            return 1;
        int res = 0;
        for(int i = 1; i <= number; i++)
            res += jumpFloorII(number - i); //递归结果相加
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n^{2})$ ，一层循环加一层递归
空间复杂度： $O (n)$ ，递归栈的空间

方法三：递归优化

具体做法：

对于方法二中的公式，因为我们有 $f (n - 1) = f (n - 2) + f (n - 3) + . . . + f ((n - 1) - (n - 2)) + f ((n - 1) - (n - 1))$ 因此可以得到结果： $f (n) = f (n - 1) + f (n - 1) = 2 * f (n - 1)$ ，由此减少递归次数。

class Solution {
public:
    int jumpFloorII(int number) {
        if(number <= 1) //1或0都是1
            return 1;
        return 2 * jumpFloorII(number - 1); //f(n) = 2*f(n-1)
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，递归公式为 $T (n) = T (n - 1) + 1$
空间复杂度： $O (n)$ ，递归栈最大深度

方法四：动态规划

具体做法：

方法三的递归也可以用数组依次往后乘2得到。

class Solution {
public:
    int jumpFloorII(int number) {
        vector<int> dp(number + 1);
        dp[0] = 1;//初始化面两个
        dp[1] = 1;
        for(int i = 2; i <= number; i++) //依次乘2
            dp[i] = 2 * dp[i - 1];
        return dp[number];
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，一次遍历
空间复杂度： $O (n)$ ，辅助数组dp

方法五：数学规律

具体做法：

从方法四，我们可以发现从第一个数1开始，后面每个数都是在前一个数的基础上乘2，所以 $f(n)=2^{n-1}$

class Solution {
public:
    int jumpFloorII(int number) {
        if(number <= 1)
            return 1;
        return pow(2, number - 1); //直接次方
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，次方运算还是需要n-1次（n为number）
空间复杂度： $O (1)$ ，无额外空间

题解 | #跳台阶扩展问题#

题目的主要信息：

方法一：暴力解法

方法二：递归

方法三：递归优化

方法四：动态规划

方法五：数学规律