手帐 Blog

主题

复盘 · LC 70 爬楼梯 ​

题目 ​

题意 ​

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

  • 输入：正整数 n（常见约束到 45）。
  • 输出：方法数。

边界：n = 1 → 1；n = 2 → 2；n 较大时纯递归会爆。

涉及算法 ​

标签一句话
一维 DP / 斐波那契f(n) = f(n-1) + f(n-2)：最后一步跨 1 或跨 2
记忆化递归用表缓存子问题，避免指数级重复计算

教程对照：21 · DP 入门 · 一维。

评价我的解法 ​

思路对：自顶向下递归 + resMap 记忆化，状态转移就是斐波那契同构。还用 console.time 测了 n = 45，说明意识到了性能。

我的代码（摘自 70-爬楼梯/index.js，不含本地测例）：

javascript
function f(n, resMap) {
  if (n < 0) {
    return 0;
  }
  if (n === 0) {
    return 1;
  }
  if (resMap[n]) {
    return resMap[n];
  }
  const res = f(n - 1, resMap) + f(n - 2, resMap);
  resMap[n] = res;
  return res;
}

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  const resMap = [];
  return f(n, resMap);
};
  • 正确性：n 阶的方法数等于「先到 n-1 再跨 1」+「先到 n-2 再跨 2」；n = 0 返回 1 表示「已经在顶/空方案」，对正整数 n 的调用是自洽的。
  • 时间 O(n)，空间 O(n)（递归栈 + 表）。
  • 可打磨：
    1. if (resMap[n]) 用真值判断：本题结果恒为正，能过；更稳妥写 resMap[n] !== undefined（或 in / has）。
    2. n < 0 → 0 对约束内输入多余；更常见的初始化是直接 f(1)=1、f(2)=2。
    3. 面试更常写自底向上滚动变量，空间 O(1)，也少谈递归深度。

小结：DP 入门答卷合格——会定义转移、会加记忆化；下一步把「递推两变量」练成默写模板。

最佳题解 ​

滚动变量一维递推：

javascript
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n <= 2) return n;
  let a = 1; // f(1)
  let b = 2; // f(2)
  for (let i = 3; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
};
  • 时间 O(n)，空间 O(1)。
  • 为何更优：同一转移方程，去掉递归栈与整张表；口述也更短——「斐波那契，只留前两项」。

等价写法：dp 数组 dp[i] = dp[i-1] + dp[i-2]，再压缩成上面两个变量。

关联题目 ​

题为何相关
509. 斐波那契数同构递推，练滚动变量
746. 使用最小花费爬楼梯爬楼梯变体：费用 + 一维 DP
198. 打家劫舍教程同篇的一维 DP 下一关

一句话带走 ​

爬楼梯 = 斐波那契：f(n)=f(n-1)+f(n-2)；能记忆化，更要会滚动两变量。