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

设置dp数组，其中dp[i] 表示当前跳道第 i 个台阶的方法数
1、最后跳 1 步到达第 n 个台阶，说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为dp[n-1]
2、最后跳 2 步到达第 n 个台阶，说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为dp[n-2]
3、同理，最后跳 n 步到达第 n 个台阶，说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为dp[0]
那么总的方法数就是所有可能的和。也就是dp[n] = dp[n-1] + dp[n-2] + ... + dp[0]，也是状态转移方程
初始条件dp[0] = dp[1] = 1

实例：

target = 4

操作	target	dp
1	0	1
2	1	1
3	2	2
4	3	4
5	4	8

最后返回结果：8

JAVA版本

public class Solution {
    public int jumpFloorII(int target) {
        // 特殊情况
        if (target == 0 || target == 1) {
            return 1;
        }
        // 定义dp数组
        int[] dp = new int[target+1];
        // 初始化
        dp[0] = dp[1] = 1;
        // 双层循环计算
        for (int i = 2; i <= target; i++){
            for (int j = 0; j < i; j++){
                // 动态转移方程
                dp[i] += dp[j];
            }
        }
        return dp[target];
    }
}

复杂度分析

时间复杂度：N表示 target，算法需要双层遍历循环时间

空间复杂度O(N)：dp数组占用空间O(N)

算法思想二：迭代(方法一优化)

解题思路：

由方法一可知：dp[n] = dp[n-1] + dp[n-2] + ... + dp[0]

则 n-1 阶台阶的方法数：dp[n-1] = dp[n-2] + ... + dp[0]

两式相减可得：dp[n] - dp[n-1] = dp[n-1] 即 dp[n] = 2 * dp[n-1]

实例;

target = 4

操作	target	res（2 * dp[n-1]）
1	0	1
2	1	1
3	2	2
4	3	4
5	4	8

最后返回结果：8

Python版本

class Solution:
    def jumpFloorII(self, number):
        # write code here
        # 初始化
        res = 1
        for i in range(2, number+1):
            # 循环计算
            res = 2 * res
        return res