爬楼梯 java 70
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3
解释：有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示： 1 <= n <= 45
思路
到第 n 阶，只能从 n-1 阶迈 1 步，或从 n-2 阶迈 2 步，所以：
f(n) = f(n-1) + f(n-2)，本质是斐波那契数列，f(1)=1，f(2)=2。
解法一：纯递归（不推荐，会超时）
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
return climbStairs(n - 1) + climbStairs(n - 2);
}
}
问题：大量重复计算，f(3) 被反复算，时间复杂度 O(2ⁿ)，n=45 直接超时。
解法二：记忆化递归（自顶向下）
class Solution {
private int[] memo;
public int climbStairs(int n) {
if (n <= 2) return n; // 边界！n=1 时数组长度 2，memo[2] 会越界
memo = new int[n + 1];
memo[1] = 1;
memo[2] = 2;
return dfs(n);
}
private int dfs(int n) {
if (memo[n] != 0) return memo[n]; // 已算过，直接返回
memo[n] = dfs(n - 1) + dfs(n - 2);
return memo[n];
}
}
复杂度：时间 O(n)（每个值只算一次），空间 O(n)（递归栈 + memo 数组）。
解法三：滚动数组迭代（最优解，推荐）
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2; // f(1), f(2)
for (int i = 3; i <= n; i++) {
int c = a + b; // 先算新值
a = b; // 再滚动，顺序不能反
b = c;
}
return b;
}
}
复杂度：时间 O(n)，空间 O(1)。
复杂度对比
| 解法 | 时间 | 空间 | 评价 |
|---|---|---|---|
| 纯递归 | O(2ⁿ) | O(n) | 超时，仅用于理解递推 |
| 记忆化递归 | O(n) | O(n) | 可过，面试追问可用 |
| 滚动数组 | O(n) | O(1) | 最优，面试推荐 |
注意事项
- 边界：
n <= 2直接返回，否则 n=1 时memo[2]数组越界 - 溢出：本题 n ≤ 45，f(45) = 1836311903 未超 int 上限；n 更大需改用 long
- 滚动顺序：先算
c = a + b，再a = b, b = c，顺序反了会覆盖数据