LeetCode 70. 爬楼梯
目录
题目描述
✅ 70. 爬楼梯
题意分析
楼梯共
n阶，每次只能向上爬 1 阶或 2 阶，问从地面爬到第n阶一共有多少种不同的走法。先明确问的是方案数，不是最少步数、也不是最小代价。这决定了聚合方式是把不同方案的数量相加，而不是取最小值。很多人第一遍读题会下意识往「最少几步」上想，那是另一道题。
再明确「不同」的判定标准：走法由每一步的步长序列决定，顺序不同就算不同方案。
n = 3时1+1+1、1+2、2+1是三种走法，不能把后两种当成同一种，答案是 3 而不是 2。约束里透露的算法信号有两点。第一，任何一条到达第
n阶的走法，它的最后一步只有两种可能——迈 1 阶，或迈 2 阶。顺着这个分解视角看，「到达某一阶」这件事只跟它前面紧邻的两阶有关，状态之间的依赖非常局部。第二，题目要的是一个纯计数结果，不要求还原任何一条具体路径，所以不必保存中间路径，只保存计数即可。这两点合起来，指向一个状态数与n同阶、每个状态常数时间转移的递推。边界情形：
n = 1时只有一种走法（爬 1 阶），答案是 1；n = 2时有1+1和2两种，答案是 2。这两个值是递推的起点，任何递推写法都必须让它们成立。另外方案数是按斐波那契速度增长的，题目的返回类型是int，说明题面限定的n范围内答案不会超出 32 位整数，实现时无需考虑大数。
解法：滚动变量动态规划
核心思路
到达第
i阶的最后一步只能来自第i - 1阶或第i - 2阶，因此dp[i] = dp[i - 1] + dp[i - 2]。转移只依赖前两个状态，用两个变量滚动保存即可。边界为第 1 阶有 1 种走法，第 2 阶有 2 种走法。
解题步骤
n <= 2时直接返回n。- 用
preTwo = 1、preOne = 2表示前两阶的方案数。- 从第 3 阶开始计算两者之和，并滚动更新变量。
- 循环结束后返回
preOne。
代码实现
class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int preTwo = 1;
int preOne = 2;
for (int step = 3; step <= n; step++) {
int cur = preOne + preTwo;
preTwo = preOne;
preOne = cur;
}
return preOne;
}
}
func climbStairs(n int) int {
if n <= 2 {
return n
}
preTwo := 1
preOne := 2
for step := 3; step <= n; step++ {
cur := preOne + preTwo
preTwo = preOne
preOne = cur
}
return preOne
}
复杂度分析
- 时间复杂度：$O(n)$，每一阶只计算一次。
- 空间复杂度：$O(1)$，只保留前两个状态。
关键点总结
- 按最后一步是 1 阶还是 2 阶分类，两类方案互斥且完整。
- 初值
1、2对应第 1、2 阶，不能套用从0、1开始的斐波那契初值。- 更新滚动变量时要保留旧值，避免覆盖仍需参与计算的状态。
易错点总结
- 未单独处理
n = 1，会错误返回第 2 阶的初值2。- 循环从第 2 阶开始或使用
< n，会多算或少算一轮。- 先覆盖
preOne再赋给preTwo，会丢失旧状态。1 + 2与2 + 1是不同顺序的两种方案，不能按组合去重。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 剑指 Offer 10- II. 青蛙跳台阶问题 | 简单 | 与本题同一递推，但要求对 1000000007 取模，需在每轮加法后立刻取模 |
| 509. 斐波那契数 | 简单 | 直接给出递推式，边界是 F(0)=0、F(1)=1，正好用来对照本题错位的初值 |
| 剑指 Offer 10- I. 斐波那契数列 | 简单 | 与 509 同题但需取模，可练「先取模再相加」避免中间量溢出 |
| 1137. 第 N 个泰波那契数 | 简单 | 依赖前三项，滚动变量从两个增到三个，检验对不变量的掌握程度 |
| 746. 使用最小花费爬楼梯 | 简单 | 每阶带代价、求最小花费，聚合从相加换成取最小，且起点可选第 0 或第 1 阶 |
| LCR 088. 使用最小花费爬楼梯 | 简单 | 与 746 同题异名，适合把「计数 DP」与「最优化 DP」的模板放在一起对比 |
| 面试题 08.01. 三步问题 | 简单 | 步长扩到 1/2/3 阶且需取模，是本题往「最近 k 项求和」方向的最小推广 |
| 91. 解码方法 | 中等 | 同样按「最后一步取 1 位还是 2 位」分类，但两条转移各带合法性判断，含 0 陷阱 |
| 198. 打家劫舍 | 中等 | 相同的「回看两格」结构，聚合换成取最大，且转移要区分选与不选当前位置 |
| 377. 组合总和 Ⅳ | 中等 | 步长集合改由输入给出，是本题的一般化；顺序敏感这一点与本题完全一致 |
| 补充题 2. 圆环回原点问题 | 中等 | 状态多一维「当前所在位置」，在环上转移，需要同时对相邻两侧累加 |