动态规划简单2 种解法

#JZ71跳台阶扩展问题

每次可跳 1 到 n 级，计算跳上 n 级台阶的不同方法数。

#动态规划#数学#牛客

解题主线

f(n)=f(0)+f(1)+...+f(n-1)，并约定 f(0)=1 作为递推空前缀。
由相邻两式可得 n>=2 时 f(n)=2f(n-1)，因此正整数 n 的答案为 2^(n-1)。

解法 1：枚举最后一步动态规划

对每一级 i，累加所有较低台阶 j 的方案数。

时间复杂度： O(n²)
空间复杂度： O(n)

JAVA

final class Solution {
    public int jumpFloorII(int n) {
        // f(i) 表示恰好到达第 i 级的方案数，f(0)=1 表示唯一的空跳法。
        // 因为 f(i) 汇总此前全部状态，所以相邻两级满足 f(i)=2*f(i-1)。
        if (n <= 0) return 0;
        int[] ways = new int[n + 1];
        ways[0] = 1;
        for (int step = 1; step <= n; step++) {
            for (int previous = 0; previous < step; previous++) {
                ways[step] = Math.addExact(ways[step], ways[previous]);
            }
        }
        return ways[n];
    }
}

解法 2：递推式压缩

从 f(1)=1 开始，每增加一级就把方案数翻倍。

时间复杂度： O(n)
空间复杂度： O(1)

JAVA

final class Solution {
    public int jumpFloorII(int n) {
        // f(i) 表示恰好到达第 i 级的方案数，f(0)=1 表示唯一的空跳法。
        // 因为 f(i) 汇总此前全部状态，所以相邻两级满足 f(i)=2*f(i-1)。
        if (n <= 0) return 0;
        int ways = 1;
        for (int step = 2; step <= n; step++) ways = Math.multiplyExact(ways, 2);
        return ways;
    }
}

实现提示

用整数递推替代旧代码的 Math.pow 强转，避免浮点精度与静默溢出。

边界与易错点

这是 Q070 文件中混入的牛客 JZ71，不应算作 LeetCode 70 的另一种解法。
Math.pow 使用 double，整数边界附近可能丢失精度；应使用整数递推并检测 int 溢出。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

easy/Q070_jumpFloor_np.java