Appearance
爬楼梯
更新: 7/5/2026 字数: 0 字 时长: 0 分钟
LeetCode 70. Climbing Stairs
题目描述
假设你正在爬楼梯，需要 阶才能到达楼顶。每次你可以爬 1 个 或 2 个 台阶。请问有多少种不同的方法可以爬到楼顶？
示例：
输入：n = 2
输出：2
解释：有两种方法爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
输入：n = 3
输出：3
解释：有三种方法爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶约束：。
思路拆解：从暴力到最优
想法一：暴力递归（自顶向下）
先问自己一个关键问题：要到达第 阶，最后一步是怎么迈上来的？
只有两种可能：
- 从第 阶迈 1 步上来；
- 从第 阶迈 2 步上来。
所以「到第 阶的方法数」= 「到第 阶的方法数」+ 「到第 阶的方法数」。这正是递推关系：
点击展开暴力解法
js
function climbStairs(n) {
if (n <= 2) return n; // 递归出口：1 阶 1 种，2 阶 2 种
return climbStairs(n - 1) + climbStairs(n - 2);
}- 时间：，指数级。因为递归树里
f(n-2)之类的子问题被重复计算了无数遍。 - 空间：，递归栈深度。
当 时，这个解法会慢到无法接受。
为什么暴力会爆炸？
画出递归树就能看到：f(5) 要算 f(4) 和 f(3)，而 f(4) 又要算 f(3) 和 f(2)……同一个 f(3) 被算了很多次。这种「大量重叠子问题」正是动态规划要解决的痛点——把每个子问题只算一次并记下来。
想法二：动态规划（自底向上，DP 表）
既然递推关系是 ，我们干脆从小到大把每一阶的方法数依次算出来，存进一个数组 dp：
dp[1] = 1（到第 1 阶只有 1 种）dp[2] = 2（到第 2 阶有 2 种）dp[i] = dp[i-1] + dp[i-2]（从第 3 阶开始递推）
核心思路
定义状态 → 找递推 → 定边界 → 顺序递推：
- 状态：
dp[i]表示「爬到第 阶的不同方法数」。 - 递推：
dp[i] = dp[i-1] + dp[i-2]——到第 阶的最后一步只能来自第 或第 阶。 - 边界：
dp[1] = 1，dp[2] = 2。 - 顺序：从 一直算到 ，答案就是
dp[n]。
这其实就是斐波那契数列！1, 2, 3, 5, 8, 13, ...——每一项都是前两项之和。
想法三：滚动变量优化（最优解）
观察递推式 dp[i] = dp[i-1] + dp[i-2]：算 dp[i] 时，只用到最近的两个值，前面的都用不上了。所以根本不需要整个数组，只用两个变量滚动往前推即可，空间从 降到 。
动态演示
下面的动画完整演示了 n = 6 时的动态规划填表全过程——看 dp 表如何从边界值出发，一格一格由前两格相加填出最终答案：
步骤 1 / 7初始化边界
正在填来源 (i-1 / i-2)已填
dp[1]
1
dp[2]
?
dp[3]
?
dp[4]
?
dp[5]
?
dp[6]
?
1
边界：到第 1 阶只有 1 种走法（迈 1 阶）。dp[1] = 1。
完整代码（JavaScript）
版本 A：DP 表（直观易懂）
js
/**
* @param {number} n
* @return {number}
*/
function climbStairs(n) {
if (n <= 2) return n; // 边界：1 阶 1 种，2 阶 2 种
const dp = new Array(n + 1);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 递推：由前两阶相加
}
return dp[n];
}版本 B：滚动变量（最优， 空间）
js
/**
* @param {number} n
* @return {number}
*/
function climbStairs(n) {
if (n <= 2) return n;
let prev = 1, cur = 2; // 分别代表 dp[i-2]、dp[i-1]
for (let i = 3; i <= n; i++) {
const next = prev + cur; // 新值 = 前两个之和
prev = cur; // 整体向右滚动一格
cur = next;
}
return cur; // cur 最终就是 dp[n]
}进阶：矩阵快速幂 O(log n)
由于爬楼梯本质是斐波那契数列，还可以用矩阵快速幂把时间压到 。递推可写成矩阵形式：
对矩阵做快速幂即可在对数时间内求出结果。本题 用不上，但在数据量极大时是标准优化手段。
复杂度分析
设台阶数为 。
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力递归 | 大量重叠子问题，会超时 | ||
| DP 表 | 每阶只算一次，需数组存储 | ||
| 滚动变量 | 只保留最近两个值，最优 | ||
| 矩阵快速幂 | 斐波那契通用加速，大 才用 |
为什么 DP 是 ？ 从 dp[3] 到 dp[n] 只需一次遍历，每一格是一次常数级加法，所以是线性时间。滚动变量进一步把「存整个数组」缩成「只存两个变量」，空间降为常数。
边界与易错点
易错点
边界初始化。
dp[1] = 1、dp[2] = 2必须写对，这是整个递推的起点，错了后面全错。有些版本会额外定义dp[0] = 1（表示「站在地面也算一种方案」），此时dp[1] = 1、dp[2] = 2依然成立。循环从 3 开始。前两阶是边界，递推要从 起，写成
i <= n（含 ），漏掉等号会少算一格。滚动时的赋值顺序。必须先用
next = prev + cur算出新值，再更新prev = cur、cur = next。如果先改prev再算next，就会用错旧值。用一个临时变量next最稳妥。n = 1或n = 2的特判。开头的if (n <= 2) return n;直接处理了小 ，避免进入循环时数组或变量越界。数据溢出（其他语言）。JS 的 Number 到 （结果约 18 亿）不会溢出；但在 C/Java 中
int可能溢出，需用long。本题范围 是安全的。不要用暴力递归提交。 时 量级必然超时，一定要用 DP 或滚动变量。
简易解题思路（记忆口诀）
「最后一步看两种，要么一阶要么两阶；到第 n 阶方法数，等于前两阶相加。」
拆开记：
| 口诀 | 对应操作 |
|---|---|
| 最后一步看两种 | 到第 阶的最后一步，只能是迈 1 阶或迈 2 阶 |
| 要么一阶要么两阶 | 分别对应从第 阶、第 阶上来 |
| 等于前两阶相加 | dp[i] = dp[i-1] + dp[i-2]，就是斐波那契 |
| 两变量滚动 | 只用 prev、cur 两个变量往右滚，空间 |
一句话记住本质：爬楼梯就是斐波那契数列——「到这一阶的方法 = 前两阶方法之和」，从下往上滚两个变量就算完了。