5.2 KiB
tags, create time
| tags | create time | |||
|---|---|---|---|---|
|
2026-05-16 18:30 |
81. 爬楼梯（Climbing Stairs）
[!quote] LeetCode 原题 · 简单 假设你正在爬楼梯。需要
n阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。问有多少种不同的方法可以爬到楼顶？
- 输入范围：
1 <= n <= 45
题面
示例 1：
输入：n = 2
输出：2
解释：有两种方法
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法
1. 1 + 1 + 1
2. 1 + 2
3. 2 + 1
思路
第一步：找递推关系
先从一个简单的问题开始——如果最后一步只有一阶或两阶两种可能，那么到达第 i 阶的方式数由什么决定？
想象你已经站在了第 i 阶的楼顶上，回顾你的最后一步：
- 如果你是从第 i-1 阶迈了 1 步上来的
- 或者从第 i-2 阶迈了 2 步上来的
除此之外没有别的可能了。所以：
dp[i] = dp[i-1] + dp[i-2]
这个递推式是不是非常熟悉？对，它就是 Fibonacci（斐波那契数列）。
graph LR
A["第 i 阶"] --> B["第 i-1 阶\n迈 1 步"]
A --> C["第 i-2 阶\n迈 2 步"]
B --> D["dp[i-1] 种方式"]
C --> E["dp[i-2] 种方式"]
A -.-> F["dp[i] = dp[i-1]\n+ dp[i-2]"]
style A fill:#e7f3ff,stroke:#3b82f6
style F fill:#fef3c7,stroke:#f59e0b
第二步：确定边界条件
递推关系有了，接下来思考——哪些位置是"起点"，它们的值应该是多少？
dp[1] = 1：只有 1 阶台阶，直接走上去，只有 1 种方式dp[2] = 2：有 2 阶台阶，可以1+1或2，有 2 种方式
这就是我们的"地基"。所有更大的 i 都从这两块砖往上垒。
第三步：自底向上填表
以 n = 5 为例，逐步填表：
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| dp[i] | — | 1 | 2 | 3 | 5 | 8 |
每一步都只是前两步之和，规律一目了然。
flowchart LR
subgraph "填表过程 n = 5"
A["dp[1] = 1"] --> B["dp[2] = 2"]
B --> C["dp[3] = 1+2 = 3"]
C --> D["dp[4] = 2+3 = 5"]
D --> E["dp[5] = 3+5 = 8"]
end
style A fill:#dbeafe,stroke:#2563eb
style E fill:#dcfce7,stroke:#16a34a
代码提示
在动手写代码之前，想一想这些关键决策点：
[!question] 💡 思考 1 需要一个完整的数组来存储所有
dp[i]吗？还是只需要记住最近两个值就够了？
当你计算 dp[i] 时，只用到了 dp[i-1] 和 dp[i-2]，之前的值全部变成了冗余。这意味着我们可以把空间复杂度从 O(n) 压缩到 O(1)。
[!question] 💡 思考 2 循环应该从
i = 3开始还是i = 1开始？为什么n = 1和n = 2不需要进循环？
当 n ≤ 2 时答案已经直接知道了，循环从第 3 阶开始填表即可。在代码中可以统一处理，也可以用边界判断提前返回。
技巧
滚动变量法（空间优化）
不需要数组！用两个变量滚动更新就够：
| 变量 | 含义 | 初始值 |
|---|---|---|
prev2 |
dp[i-2] | 1（dp[1]） |
prev1 |
dp[i-1] | 2（dp[2]） |
每一步计算 cur = prev1 + prev2，然后往前滚：
prev2 = prev1
prev1 = cur
就像你在爬楼梯，每次只看眼前这 2 步就够了——「贪心不看全图，动态只看相邻」。
递归 vs 迭代
| 方法 | 时间 | 空间 | 评价 |
|---|---|---|---|
| 朴素递归 | O(2ⁿ) | O(n) | 有大量重复子问题，会超时 |
| 记忆化递归 | O(n) | O(n) | 加缓存就行，但递归栈开销不小 |
| 自底向上 DP | O(n) | O(n) | 标准写法，清晰直观 |
| 滚动变量 DP | O(n) | O(1) | 最优推荐 ✅ |
代码
Go 语言实现
// climbStairs returns the number of distinct ways to climb n stairs.
// You can take either 1 or 2 steps at a time.
func climbStairs(n int) int {
// 边界情况：1 阶或 2 阶直接返回
if n <= 2 {
return n
}
// 滚动变量：只需要记住前两个值
prev2 := 1 // dp[1]
prev1 := 2 // dp[2]
// 从第 3 阶开始依次计算
for i := 3; i <= n; i++ {
cur := prev1 + prev2 // dp[i] = dp[i-1] + dp[i-2]
prev2 = prev1 // 滚动向前
prev1 = cur
}
return prev1
}
执行过程演示（n = 5）
初始: prev2=1, prev1=2
i=3: cur=2+1=3 → prev2=2, prev1=3
i=4: cur=3+2=5 → prev2=3, prev1=5
i=5: cur=5+3=8 → prev2=5, prev1=8
返回 prev1 = 8 ✅
复杂度分析
- 时间复杂度：O(n) — 单层循环，做 n-2 次加法
- 空间复杂度：O(1) — 仅使用三个整型变量
举一反三
这道题本质上是 Fibonacci 数列的第一道入门 DP。它的核心模式 —— 「当前状态 = 前几个状态的组合」 —— 会在很多题目中重复出现：
- 13-最大子数组和 — 同样是线性 DP，思考"选或不选"
- 接龙类问题 — 同样考虑最后一步的多种选择
[!summary] 📌 本节要点
- 找清递推关系：最后一步只有两种选择
- 确定边界：dp[1]=1, dp[2]=2
- 空间优化：滚动变量替代数组，O(n)→O(1)