算法 - 爬楼梯 (Climbing Stairs)

Posted on

1. 题目

假设你正在爬楼梯，需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。问共有多少种不同的方法可以爬到楼顶？

示例:

1
2
输入: n = 2  -> 输出: 2  （1+1, 2）
输入: n = 3  -> 输出: 3  （1+1+1, 1+2, 2+1）

2. 解题思路

到达第 n 阶的最后一步，要么从第 n-1 阶跨 1 步上来，要么从第 n-2 阶跨 2 步上来，两者互斥且覆盖所有情况：

1
f(n) = f(n-1) + f(n-2)

这就是斐波那契数列，f(1)=1, f(2)=2。

  • 直接递归会有大量重复子问题，指数级 O(2ⁿ)，需要记忆化或自底向上 DP。
  • 由于 f(n) 只依赖前两项，可用两个变量滚动，把空间优化到 O(1)。

DP 五步（入门示范）：

  1. 状态定义：dp[i] = 到第 i 阶的方法数。
  2. 转移方程：dp[i] = dp[i-1] + dp[i-2]。
  3. 初始化：dp[1]=1, dp[2]=2。
  4. 遍历顺序：从小到大。
  5. 返回值：dp[n]。
  • 时间复杂度：O(n)；空间复杂度：O(1)（滚动变量版）。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 滚动变量（最优：O(n) 时间 / O(1) 空间）
function climbStairs(n: number): number {
    if (n <= 2) return n;
    let prev = 1; // f(i-2)
    let curr = 2; // f(i-1)
    for (let i = 3; i <= n; i++) {
        const next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

// 记忆化递归（自顶向下）
function climbStairsMemo(n: number, memo: Map<number, number> = new Map()): number {
    if (n <= 2) return n;
    if (memo.has(n)) return memo.get(n)!;
    const res = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
    memo.set(n, res);
    return res;
}

console.log(climbStairs(3)); // 3
console.log(climbStairs(5)); // 8

4. 面试延伸

  • 变形：每次可爬 1..k 阶 —— dp[i] = sum(dp[i-1] ... dp[i-k])，滑动窗口求和。
  • 最小花费爬楼梯（746）：把「计数」换成「求最优（min）」，是 DP 的另一大流派。
  • 不同路径（62 网格）/ 打家劫舍（198）：转移方程类似，考察你能否从题面识别出「斐波那契结构」。
  • 追问「为什么不能用组合数直接算」：可以，Σ C(n-k, k)，但要处理大数与取模，DP 更稳更通用。
  • 若面试官提到溢出 / 取模 1e9+7，说明考的是大数斐波那契 + 矩阵快速幂（O(log n)）。

难度：简单 | LeetCode 70 题 | 动态规划 Hello World