动态规划（5 题）

DP 四步：定义状态 -> 写转移方程 -> 初始化 -> 确定遍历顺序。 面试说不清「状态定义」，基本就挂了。先说 dp[i] 的含义，再写方程。 返回目录：4.algorithms/题单.md

1. 爬楼梯

题意：每次爬 1 或 2 阶，爬到 n 阶有多少种方法。 思路：f(n) = f(n-1) + f(n-2)，就是斐波那契。用两个滚动变量省掉数组。 复杂度：时间 O(n)，空间 O(1)。 易错：JS 里 [a, b] = [b, a + b] 是解构赋值，右值先全部算完再赋值，可以放心用。 追问：「还能优化吗？」——矩阵快速幂 O(log n)，面试一般不要求。

function climbStairs(n) {
  if (n <= 2) return n;
  let a = 1; // f(1)
  let b = 2; // f(2)
  for (let i = 3; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

2. 打家劫舍

题意：不能偷相邻两家，求能偷到的最大金额。 思路：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，同样用滚动变量。 复杂度：时间 O(n)，空间 O(1)。 易错：prev, cur 必须同时更新（解构赋值），否则会用到已经改过的值。

function rob(nums) {
  let prev = 0; // dp[i-2]
  let cur = 0; // dp[i-1]
  for (const v of nums) {
    [prev, cur] = [cur, Math.max(cur, prev + v)];
  }
  return cur;
}

3. 最长递增子序列

题意：求最长严格递增子序列的长度。 思路：贪心 + 二分。tails[i] 表示长度为 i+1 的递增子序列的最小结尾，结尾越小越有前途。 复杂度：时间 O(n log n)，空间 O(n)。 易错：这题不是标准 DP，标准 DP 是 O(n^2)；面试写 O(n log n) 更亮眼，但要能讲清 tails 的含义。 易错：tails[lo] = v 在下标等于长度时等价于 append，JS 数组会自动扩容。 追问：「要输出具体序列怎么办？」——记录每个位置的 pre 下标回溯，或改用 O(n^2) 的 DP。

function lengthOfLIS(nums) {
  const tails = [];
  for (const v of nums) {
    // 在 tails 里找第一个 >= v 的位置
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < v) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = v; // lo === tails.length 时就是追加
  }
  return tails.length;
}

4. 零钱兑换

题意：用最少的硬币凑出 amount，凑不出返回 -1。 思路：完全背包。dp[i] = 凑出金额 i 的最少硬币数。 复杂度：时间 O(amount * coins.length)，空间 O(amount)。 易错：初始化成 Infinity 表示不可达，最后要判断是否还是 Infinity。 易错：循环顺序——外层金额、内层硬币，这样每种硬币可以用无限次。

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i && dp[i - c] + 1 < dp[i]) {
        dp[i] = dp[i - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

5. 编辑距离

题意：把 word1 变成 word2 的最少操作数（增、删、改）。 思路：dp[i][j] = word1 前 i 个字符转成 word2 前 j 个字符的最小操作数。字符相同就继承左上角，不同就取「增删改」三者的最小值 + 1。 复杂度：时间 O(m * n)，空间 O(n)（滚动数组）。 易错：滚动数组时要用 prev 保存左上角的值，写错就变成另一道题了。 易错：初始化——dp[j] = j 表示空串变成长度 j 需要插入 j 次。

function minDistance(word1, word2) {
  const m = word1.length;
  const n = word2.length;
  const dp = new Array(n + 1);
  for (let j = 0; j <= n; j++) dp[j] = j;

  for (let i = 1; i <= m; i++) {
    let prev = dp[0]; // 左上角 dp[i-1][j-1]
    dp[0] = i; // 空串变成 word1 前 i 个字符
    for (let j = 1; j <= n; j++) {
      const tmp = dp[j]; // 保存 dp[i-1][j]
      if (word1[i - 1] === word2[j - 1]) {
        dp[j] = prev; // 不用操作
      } else {
        dp[j] = Math.min(prev, dp[j], dp[j - 1]) + 1; // 改 / 删 / 增
      }
      prev = tmp;
    }
  }
  return dp[n];
}