70. 爬楼梯
题目描述
假设你正在爬楼梯。需要 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 阶
解题思路
第一步：理解问题本质
这是一个经典的动态规划问题，也是斐波那契数列的变种。
关键点：爬到第 n 阶的最后一步，可能是从第 n-1 阶跨 1 步，或从第 n-2 阶跨 2 步。
第二步：暴力递归
思路：直接根据定义递归求解。
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
缺点：大量重复计算，时间复杂度指数级。
第三步：最优解法 —— 动态规划（滚动数组）
核心洞察：
f(n) = f(n-1) + f(n-2)- 只需要保存前两个状态，可以用滚动数组优化空间
状态转移方程：
f(n) = f(n-1) + f(n-2)
初始条件：
f(0) = 1（地面有一种方法：不动）f(1) = 1（只有1阶，只有一种方法）
完整代码实现
class Solution:
"""
爬楼梯 - 动态规划
核心思想：
爬到第 n 阶楼梯的方法数 = 爬到第 n-1 阶的方法数 + 爬到第 n-2 阶的方法数
因为最后一步可以跨1阶或2阶。
状态转移方程：
f(n) = f(n-1) + f(n-2)
初始条件：
f(0) = 1（地面有一种方法：不动）
f(1) = 1（只有1阶，只有一种方法）
空间优化：
只需要保存前两个状态，用滚动数组将空间复杂度优化到 O(1)
时间复杂度：O(n)
空间复杂度：O(1)
"""
def climbStairs(self, n: int) -> int:
# f0 表示 f(n-2)，f1 表示 f(n-1)
f1 = f0 = 1
for i in range(2, n + 1):
new_f = f1 + f0 # f(n) = f(n-1) + f(n-2)
f0 = f1 # 更新 f(n-2) 为 f(n-1)
f1 = new_f # 更新 f(n-1) 为 f(n)
return f1
示例推演
以 n = 5 为例：
| n | f(n) | 说明 |
|---|---|---|
| 0 | 1 | 初始条件 |
| 1 | 1 | 只有1种方法：1 |
| 2 | 2 | 1+1 或 2 |
| 3 | 3 | 1+1+1, 1+2, 2+1 |
| 4 | 5 | 斐波那契数列 |
| 5 | 8 | ... |
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力递归 | O(2^n) | O(n) | 有大量重复计算 |
| 记忆化搜索 | O(n) | O(n) | 自顶向下 |
| 动态规划（最优） | O(n) | O(1) | 滚动数组优化 |
易错点总结
1. 初始条件
注意 f(0) = 1，不是 0。这是为了统一递推公式。
2. 滚动数组的更新顺序
new_f = f1 + f0 # 先计算新值
f0 = f1 # 再更新 f0
f1 = new_f # 最后更新 f1