194 lines
5.2 KiB
Markdown
194 lines
5.2 KiB
Markdown
---
|
||
tags: [算法/动态规划, 基础DP, Fibonacci]
|
||
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（斐波那契数列）**。
|
||
|
||
```mermaid
|
||
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** |
|
||
|
||
每一步都只是前两步之和，规律一目了然。
|
||
|
||
```mermaid
|
||
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 语言实现
|
||
|
||
```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] 📌 本节要点
|
||
> 1. 找清递推关系：最后一步只有两种选择
|
||
> 2. 确定边界：dp[1]=1, dp[2]=2
|
||
> 3. 空间优化：滚动变量替代数组，O(n)→O(1)
|