子问题视角：分治与动态规划

子序列类型问题

先选模板，再推方程

动态规划解题框架里说过： 方程写不出来，九成是状态定义错了。

子序列这一类题的状态定义有两套固定模板。绝大多数题不需要你原创， 只需要选对是哪一套：

  • 「以 i 结尾」 —— dp[i] 表示必须包含 nums[i] 的答案
  • 「前 i 个」 —— dp[i] 表示只看前 i 个元素时的答案

⭐ 这两套的差别不只是措辞。它们的数组长度、索引对应关系、答案在哪一格 全都不一样，混用会得到一个「几乎对」的结果 —— 这是子序列题最常见的错法。

模板一：以 i 结尾 —— 最长递增子序列

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;

  // dp[i] = 以 nums[i] 结尾的最长递增子序列长度
  const dp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);       // 🚨 不是 dp[n-1]
}

🚨 答案是 Math.max(...dp)，不是 dp[n-1]。 这是这套模板的标志性陷阱。

因为定义里写死了「必须以 nums[i] 结尾」，而最长的那条子序列不一定 恰好在最后一个元素结束。拿 [1,3,6,7,9,4,10,5,6] 跑一遍，把整个 dp 打出来：

nums = [ 1, 3, 6, 7, 9, 4, 10, 5, 6]
dp   = [ 1, 2, 3, 4, 5, 3,  6, 4, 5]
                            ↑        ↑
                        max=6     dp[n-1]=5

真正的答案 6 出现在 dp[6]（以 10 结尾的 1,3,6,7,9,10）， 而 dp[8] 只有 5（1,3,4,5,6）。返回 dp[n-1] 会少一个。

⚠️ 这个错在递增数组上完全不出现 —— [1,2,3,4] 的 LIS 就是以最后一个元素结尾的， dp[n-1] 恰好等于答案。实测长度 1~60 的严格递增数组，dp[n-1] 恒等于 max(dp)， 一个反例都没有；带重复的非严格递增（[1,2,2,3,3,3,4]）同样不暴露。 所以拿顺序样例自测测不出来。

⭐ 但换成随机数组它藏不住。每档 5000 组随机数组，dp[n-1] ≠ max(dp) 的比例：

长度        5      10      20      50
暴露率   31.8%   49.2%   63.8%   74.9%
平均少算  1.28    1.85    2.71    4.39
最多少算     3       5       9      14

👉 它难写对，但不难发现 —— 随手测几组无序数据就有三到七成会露馅。 真正危险的是只拿 [1,2,3,4] 这种顺手样例自测：那是它唯一的盲区。

O(n log n) 的那个版本

function lengthOfLISFast(nums) {
  const tails = [];                   // tails[k] = 长度为 k+1 的递增子序列的最小结尾

  for (const x of nums) {
    // 二分找第一个 >= x 的位置
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x;                    // 找不到就是追加，找到就替换
  }

  return tails.length;
}

⚠️ tails 不是那条最长递增子序列本身，只是长度对。 它里面装的是「各种长度下最小的结尾值」，随时在被替换。 想要子序列本身，还得另记前驱下标。

拿上面那个数组跑一遍，两者摆在一起看：

nums          = [1, 3, 6, 7, 9, 4, 10, 5, 6]
tails 最终内容 = [1, 3, 4, 5, 6, 10]      长度 6 ✅
真实的 LIS     = [1, 3, 6, 7, 9, 10]      长度 6 ✅
                       ↑  ↑  ↑
                     从第三个元素起完全对不上

🚨 长度对得上，内容一个都不能信。而且 tails 甚至不是 nums 的子序列 （4 在 nums 里排在 10 前面，但 tails 里 4 之后还有 5,6 —— 这几个值在原数组里的 顺序根本连不成一条）。实测随机数组，tails 连子序列都算不上的比例：

长度            8       15      30
不是子序列   52.1%   80.8%   97.7%

⭐ 长度越大越不可信。小数组上有一半概率碰巧对，这正是它容易被误当成答案的原因。

📌 面试里 O(n²) 那版足够，能顺口说出「还有个二分的 O(n log n) 做法」是加分。 真被要求写，注意上面这条 —— 说错「tails 就是答案」比不知道这个做法更减分。

那行 tails[mid] < x：一个等号决定严格还是非严格

< 求的是严格递增（相等元素不能接），改成 <= 求的是非严格递增。 两版各自与 O(n²) 参照对照 4000 组含重复元素的数组，各自 4000/4000 一致 —— 两个都对，只是在答不同的题。

[1, 2, 2, 3, 3, 3]     tails[mid] <  x  →  3   （严格）
                       tails[mid] <= x  →  6   （非严格）

含重复元素的数组 4000 组，两种口径答案不同的：3219 组 = 80.5%
无重复元素的数组 2000 组，两种口径答案相同的：2000 组 = 100%

🚨 无重复元素时两种写法结果完全一样。 LIS 的常见样例（包括本篇那个）恰好都没有重复值， 所以写错了自测一路绿灯，碰上「不下降子序列」这类要求非严格的题才整片错。 ⭐ 判据：题面出现「不减 / 非递减 / 允许相等」时，先去改那一个等号。

模板二：前 i 个 —— 最长公共子序列

两个字符串的题基本都用二维的「前 i 个」模板。

function longestCommonSubsequence(s1, s2) {
  const m = s1.length, n = s2.length;

  // dp[i][j] = s1 的前 i 个字符 与 s2 的前 j 个字符 的 LCS 长度
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {       // 🚨 第 i 个字符是 s1[i-1]
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

🚨 数组开 m+1 行，但第 i 个字符是 s1[i-1]。 这个错位是「前 i 个」模板的税， 也是差一错误的重灾区。

多开的那一行一列不是浪费，是为了让 base case 自然成立： dp[0][j] 表示「s1 一个字符都不取」，LCS 显然是 0 —— 这正是 fill(0) 的默认值， 一行初始化代码都不用写。如果数组只开 m 行，你就得手写第一行第一列的边界， 而那部分逻辑比多开一行难写得多。

编辑距离：base case 不能全是 0

function minDistance(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  // 🚨 base case：一个串为空时，编辑距离 = 另一个串的长度
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];              // 啥也不用做
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1],   // 替换
          dp[i - 1][j],       // 删除 s1 的第 i 个
          dp[i][j - 1],       // 插入 s2 的第 j 个
        );
      }
    }
  }

  return dp[m][n];
}

🚨 跟 LCS 不同，这里必须显式写 base case。dp[i][0] = i 的含义是 「把长度为 i 的串变成空串，要删 i 次」。

⚠️ 忘了写会怎样：dp 全是 0 起步，于是算出来的距离偏小。 「偏小」这条实测过 20000 组随机串对，错法一次都没有偏大，方向是稳定的。

但「长度相近就没事」是想当然。按 |len(s1) − len(s2)| 分档，各档的出错率：

长度差     0      1      2      3      4      5+
出错率  44.5%  80.8%  94.9%  99.2%  100%   100%
少算量   1.19   1.20   1.74   2.49   3.39   4.4 ~ 8.0

🚨 长度相等时仍有约一半会错（等长 1~8 单独跑 30000 组：49.95%）。 长度差 ≥4 就是 100% —— 不是「才明显错」，是必错。 而 ("horse","ros") 这个经典样例正好在错的那半边：

minDistance("horse", "ros")           = 3    ✅
忘写 base case 的版本                  = 2    ❌ 少 1

⭐ 真正的欺骗性不在「蒙对」，在误差只有 1。长度相近时平均少算 1.19， 答案看着就像「差不多对」，容易被当成边界没想清楚而不是缺了 base case。 📌 最干净的自测：("abcdef", "") —— 正确答案 6，错法直接返回 0。 一个串为空时误差等于另一个串的长度，一眼就能看出来。

⭐ 记忆锚点：LCS 的 base case 恰好是 0，所以能省；编辑距离不是 0，所以不能省。 别把「LCS 不用写 base case」这个经验迁移过来。

两套模板对照

以 i 结尾 前 i 个
dp 长度 n n + 1
索引对应 dp[i] ↔ nums[i] dp[i] ↔ nums[i-1]
答案在哪 max(dp) dp[n]
base case dp 初值（如 fill(1)） 第 0 行 / 第 0 列
典型题 LIS、最大子数组和 LCS、编辑距离、背包

⭐ 表里「答案在 max(dp)」不是 LIS 一道题的特例，是模板一的共性。 最大子数组和用同一套模板，同一个坑：

nums = [-2,  1, -3,  4, -1,  2,  1, -5,  4]
dp   = [-2,  1, -2,  4,  3,  5,  6,  1,  5]
                                 ↑          ↑
                             max=6      dp[n-1]=5

随机数组上 dp[n-1] ≠ max(dp) 的比例
  长度      5      10      20      50
        61.6%   73.1%   81.4%   89.9%

全正数数组 2000 组：暴露 0 组

👉 盲区也同型：LIS 是递增数组测不出来，最大子数组和是全正数数组测不出来 —— 都是「最优解恰好在最后一格结束」的那类输入。自测时专门避开它们。

👉 怎么选：子序列必须“锚定”在某个具体元素上，用「以 i 结尾」； 可以自由取舍、只关心前面看了多少，用「前 i 个」。

LIS 里 dp[i] 不锚定 nums[i] 的话，nums[j] < nums[i] 这个转移条件就没法写 —— 你根本不知道前一个子序列结尾是什么值。这就是它必须用第一套模板的原因。

下一步

背包问题用的是「前 i 个」模板的二维版， 但它有一个别的题都没有的坑：遍历顺序会改变问题的定义。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。