跳台阶扩展问题

题目的主要信息：

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

举一反三：

学习完本题的思路你可以解决如下题目：

JZ69. 跳台阶

JZ10. 斐波那契数列

JZ70. 矩形覆盖

方法一：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

思路：

对于最后一级台阶，我们可以由倒数第二级台阶跳1步，也可以由倒数第三级太极跳两步，即$f(n)=f(n-1)+f(n-2)+\mathrm{.}\mathrm{.}\mathrm{.}+f(n-(n-1))+f(n-n)=f(0)+f(1)+f(2)+\mathrm{.}\mathrm{.}\mathrm{.}+f(n-1)f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)=f(0)+f(1)+f(2)+...+f(n-1)$，因为$f(n-1)=f(n-2)+f(n-3)+\mathrm{.}\mathrm{.}\mathrm{.}+f((n-1)-(n-2))+f((n-1)-(n-1))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\ast f(n-1)f(n)=f(n-1)+f(n-1)=2*f(n-1)$，因此每级台阶方案数是前面一级台阶方案数的2倍。

具体做法：

• step 1：使用动态规划数组，下标i表示第i级台阶的方案数。
• step 2：初始化前面两个，即0级一种，1级一种。
• step 3：遍历后续，后一个是前一个的两倍。

Java实现代码：

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

C++实现代码：

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

Python实现代码：

class Solution:
    def jumpFloorII(self , number: int) -> int:
        dp = [0 for i in range(number + 1)]
        #初始化前面两个
        dp[0] = 1
        dp[1] = 1
        #依次乘2
        for i in range(2, number + 1):
            dp[i] = 2 * dp[i - 1]
        return dp[number]

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为台阶数，一次遍历
• 空间复杂度：$O(n)O(n)$，辅助数组dp的长度为$nn$

方法二：递归（扩展思路）

思路：

根据上述思路，我们还可以从后往前，因为$f(n)=2\ast f(n-1)f(n)=2*f(n-1)$，相当于找到子问题，其答案的两倍就是父问题的答案。

• 终止条件： 递归进入0或者1，可以直接得到方案数为1.
• 返回值： 将本级子问题得到的方案数的两倍返回给父问题。
• 本级任务： 进入台阶数减1的子问题。

具体做法：

• step 1：若是number为1或者0，直接放回1种方案数。
• step 2：其他情况返回子问题答案的2倍。

图示：

Java实现代码：

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

C++实现代码：

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

Python实现代码：

class Solution:
    def jumpFloorII(self , number: int) -> int:
        #1或0都是1种
        if number <= 1:
            return 1
        #f(n) = 2*f(n-1)
        return 2 * self.jumpFloorII(number - 1)

复杂度分析：

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

方法三：数学规律（扩展思路）

思路：

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

具体做法：

• step 1：首先判断number是否小于等于1，如果是，直接得出答案。
• step 2：计算$f(n)=2^{n-1}f(n)=2^\{n-1\}$。

Java实现代码：

import java.util.*;
public class Solution {
    public int jumpFloorII(int target) {
        if(target <= 1)
            return 1;
        //直接次方
        return (int)Math.pow(2, target - 1); 
    }
}

C++实现代码：

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

Python实现代码：

class Solution:
    def jumpFloorII(self , number: int) -> int:
        if number <= 1:
            return 1
        #直接次方
        return 2 ** (number - 1)

复杂度分析：

• 时间复杂度：$O(n)O(n)$，次方运算还是需要n-1次（n为number）
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间