跳到主要内容

爬楼梯

问题​

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

示例：

输入：n = 2
输出：2
解释：有两种方法：1 + 1 和 2

输入：n = 3
输出：3
解释：有三种方法：1+1+1、1+2、2+1

输入：n = 4
输出：5
解释：1+1+1+1、1+1+2、1+2+1、2+1+1、2+2

来源：LeetCode 70. 爬楼梯

答案​

核心思想

到达第 n 阶的方式 = 从第 n-1 阶爬 1 步 + 从第 n-2 阶爬 2 步。这就是经典的斐波那契数列！

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

其中 f(1)=1,f(2)=2f(1) = 1, f(2) = 2

方法一：动态规划（推荐）​

climbStairsDP.ts
function climbStairs(n: number): number {
  if (n <= 2) return n;

  const dp: number[] = 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];
}

表格推演：

n1234567
dp[n]123581321

复杂度：

  • 时间：O(n)O(n)
  • 空间：O(n)O(n)

方法二：空间优化（最优）​

只需要前两个值，不必保存整个数组：

climbStairsOptimal.ts
function climbStairs(n: number): number {
  if (n <= 2) return n;

  let prev2 = 1; // f(n-2)
  let prev1 = 2; // f(n-1)

  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}
复杂度分析
  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1) — 只用了两个变量

这是最优解，面试推荐写这个。

方法三：递归 + 记忆化​

最直观但需要优化的方法。先看暴力递归的问题，再用记忆化解决。

暴力递归（超时）：

climbStairsBruteForce.ts
// ❌ 会超时！仅展示思路
function climbStairs(n: number): number {
  if (n <= 2) return n;
  return climbStairs(n - 1) + climbStairs(n - 2);
}
                    f(5)
                 /        \
              f(4)         f(3)
             /    \       /    \
          f(3)   f(2)  f(2)   f(1)
         /    \
      f(2)   f(1)

大量重复计算！f(3) 算了 2 次，f(2) 算了 3 次

记忆化递归：

climbStairsMemo.ts
function climbStairs(n: number): number {
  const memo = new Map<number, number>();

  function helper(n: number): number {
    if (n <= 2) return n;
    if (memo.has(n)) return memo.get(n)!;

    const result = helper(n - 1) + helper(n - 2);
    memo.set(n, result);
    return result;
  }

  return helper(n);
}

复杂度：

  • 时间：O(n)O(n) — 每个子问题只计算一次
  • 空间：O(n)O(n) — 记忆化数组 + 递归栈

方法四：矩阵快速幂（了解即可）​

利用矩阵乘法加速斐波那契计算：

[f(n)f(n−1)]=[1110]n−1[f(1)f(0)]\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} f(1) \\ f(0) \end{bmatrix}
climbStairsMatrix.ts
type Matrix = number[][];

function multiply(a: Matrix, b: Matrix): Matrix {
  return [
    [
      a[0][0] * b[0][0] + a[0][1] * b[1][0],
      a[0][0] * b[0][1] + a[0][1] * b[1][1],
    ],
    [
      a[1][0] * b[0][0] + a[1][1] * b[1][0],
      a[1][0] * b[0][1] + a[1][1] * b[1][1],
    ],
  ];
}

function matPow(mat: Matrix, n: number): Matrix {
  let result: Matrix = [[1, 0], [0, 1]]; // 单位矩阵
  while (n > 0) {
    if (n % 2 === 1) result = multiply(result, mat);
    mat = multiply(mat, mat);
    n = Math.floor(n / 2);
  }
  return result;
}

function climbStairs(n: number): number {
  if (n <= 2) return n;
  const mat: Matrix = [[1, 1], [1, 0]];
  const result = matPow(mat, n - 1);
  return result[0][0] * 2 + result[0][1] * 1; // f(2)=2, f(1)=1
}
时间复杂度 O(log⁡n)O(\log n)

矩阵快速幂方法时间复杂度为 O(log⁡n)O(\log n)，对于极大的 n 有优势。面试中知道有这个方法即可，一般不会要求手写。

常见面试追问​

Q1: 如果每次可以爬 1、2、3 阶呢？​

答案：状态转移方程扩展为 f(n)=f(n−1)+f(n−2)+f(n−3)f(n) = f(n-1) + f(n-2) + f(n-3)：

function climbStairs(n: number): number {
  if (n <= 2) return n;
  if (n === 3) return 4;

  let a = 1, b = 2, c = 4;
  for (let i = 4; i <= n; i++) {
    const temp = a + b + c;
    a = b;
    b = c;
    c = temp;
  }
  return c;
}

Q2: 如果某些台阶不能踩呢？​

答案：将不能踩的台阶标记为 0：

function climbStairsWithObstacles(
  n: number,
  obstacles: Set<number>
): number {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;

  for (let i = 1; i <= n; i++) {
    if (obstacles.has(i)) {
      dp[i] = 0; // 障碍台阶方案数为 0
    } else {
      dp[i] = dp[i - 1] + (i >= 2 ? dp[i - 2] : 0);
    }
  }

  return dp[n];
}

Q3: 如果需要恰好走完 k 步？​

答案：增加一个维度，dp[i][j] 表示走 j 步到达第 i 阶的方案数：

function climbStairsExactSteps(n: number, k: number): number {
  // dp[i][j]：到第 i 阶恰好用 j 步的方案数
  const dp: number[][] = Array.from(
    { length: n + 1 },
    () => new Array(k + 1).fill(0)
  );
  dp[0][0] = 1;

  for (let j = 1; j <= k; j++) {
    for (let i = 1; i <= n; i++) {
      dp[i][j] = dp[i - 1][j - 1] + (i >= 2 ? dp[i - 2][j - 1] : 0);
    }
  }

  return dp[n][k];
}

Q4: 爬楼梯和斐波那契数列有什么关系？​

答案：

斐波那契数列爬楼梯
递推公式f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)相同
初始值f(0)=0,f(1)=1f(0)=0, f(1)=1f(1)=1,f(2)=2f(1)=1, f(2)=2
本质爬楼梯的 f(n)f(n) 就是斐波那契的 F(n+1)F(n+1)

Q5: 爬楼梯的最小代价？​

答案：LeetCode 746，每个台阶有一个代价：

function minCostClimbingStairs(cost: number[]): number {
  const n = cost.length;
  let prev2 = 0;
  let prev1 = 0;

  for (let i = 2; i <= n; i++) {
    const curr = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}

相关链接​