动态规划简单2 种解法
#70爬楼梯
每次爬 1 或 2 级台阶，计算到达第 n 级的不同方法数。
#动态规划#斐波那契
原题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示：
1 <= n <= 45
解题主线
- 最后一步只可能来自 n - 1 或 n - 2，因此 f(n) = f(n - 1) + f(n - 2)。
解法 1：动态规划数组
从 f(1)=1、f(2)=2 递推到 n。
-
时间复杂度： O(n)
-
空间复杂度： O(n)
final class Solution {
public int climbStairs(int n) {
// 状态 f(step) 表示恰好到达第 step 级的方法数，来源只有前一级和前两级。
// 从小到大递推可保证计算当前状态时，两个前驱状态都已确定。
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];
}
}解法 2：滚动变量
递推只依赖前两项，用两个变量压缩状态。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
final class Solution {
public int climbStairs(int n) {
// 状态 f(step) 表示恰好到达第 step 级的方法数，来源只有前一级和前两级。
// 从小到大递推可保证计算当前状态时，两个前驱状态都已确定。
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