动态规划简单2 种解法

#70爬楼梯

每次爬 1 或 2 级台阶，计算到达第 n 级的不同方法数。

#动态规划#斐波那契

解题主线

最后一步只可能来自 n - 1 或 n - 2，因此 f(n) = f(n - 1) + f(n - 2)。

解法 1：动态规划数组

从 f(1)=1、f(2)=2 递推到 n。

时间复杂度

O(n)

空间复杂度

O(n)

70. 爬楼梯 · 动态规划数组

java

final class Solution {
    public int climbStairs(int n) {
        if (n <= 0) return 0;
        if (n <= 2) return n;
        int[] ways = new int[n + 1];
        ways[1] = 1;
        ways[2] = 2;
        for (int step = 3; step <= n; step++) {
            ways[step] = ways[step - 1] + ways[step - 2];
        }
        return ways[n];
    }
}

从 f(1)=1、f(2)=2 递推到 n。

解法 2：滚动变量

递推只依赖前两项，用两个变量压缩状态。

时间复杂度

O(n)

空间复杂度

O(1)

70. 爬楼梯 · 滚动变量

java

final class Solution {
    public int climbStairs(int n) {
        if (n <= 0) return 0;
        int previous = 0;
        int current = 1;
        for (int step = 1; step <= n; step++) {
            int next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }
}

递推只依赖前两项，用两个变量压缩状态。

边界与易错点

本题只能跳 1 或 2 级，不要与同文件中可跳 1..n 级的牛客 JZ71 混为一题。
LeetCode 约束 n >= 1。

整理来源

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

easy/Q070_jumpFloor_np.java