子序列问题：LIS、LCS 与编辑距离

子序列类 DP 是面试高频区，本文按"单串 → 双串 → 编辑距离 → 区间"四步递进。其中 1143 和 72 常被并称两大 DP 难题，把它们的状态定义想透了，双串 DP 就通了。

一、最长递增子序列 LIS（300）

解法一：O(n²) 经典 DP

状态定义：dp[i] 表示"以 nums[i] 结尾"的最长递增子序列长度。注意必须以 i 结尾，否则无法递推。

转移：在 i 之前找所有比 nums[i] 小的位置 j，接上去：dp[i] = max(dp[j] + 1)，j 满足 0 <= j < i 且 nums[j] < nums[i]；没有更小的就初始化为 1（自己单独成序列）。

public int lengthOfLIS(int[] nums) {
    int n = nums.length, ans = 1;
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) dp[i] = 1;     // 每个元素至少自成一段
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);            // 答案是所有结尾中的最大值
    }
    return ans;
}

解法二：贪心 + 二分，O(nlogn)

维护一个数组 tails：tails[k] 表示"长度为 k+1 的递增子序列中，结尾元素的最小可能值"。tails 恒有序。遍历数组，用二分查找决定新元素去哪：

• 比 tails 末尾大 → 直接追加（LIS 变长）；
• 否则替换掉 tails 中第一个 ≥ 它的位置（让同长度结尾更小，给后续留机会）。

public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int num : nums) {
        int lo = 0, hi = size;                 // 二分找第一个 >= num 的位置
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < num) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = num;
        if (lo == size) size++;                // 追加在末尾，长度 +1
    }
    return size;
}

注意：tails 本身不是某条真实的 LIS，只有长度是可靠的。674. 最长连续递增序列是简化版——要求连续，dp 只需和前一项比较，O(n) 一遍扫描即可。

二、双串 DP 模板：LCS（1143）与不同子序列（115）

1143. 最长公共子序列

dp 表画法：dp[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。画一张 text1 为行、text2 为列 的表，逐格填：

        ""  a   c   e
    ""   0  0   0   0
    a    0  1   1   1        ← a 与 ace 的公共部分
    b    0  1   1   1        ← b 不匹配，继承左边/上边较大值
    c    0  1   2   2        ← c 匹配，左上角 +1
    d    0  1   2   2
    e    0  1   2   3        ← e 匹配，左上角 +1 → 答案 3 ("ace")

转移方程一目了然：

• t1[i-1] == t2[j-1]：字符匹配，从左上角延续 dp[i-1][j-1] + 1；
• 不相等：分别丢弃行尾或列尾字符，取 max(dp[i-1][j], dp[i][j-1])。

public int longestCommonSubsequence(String t1, String t2) {
    int m = t1.length(), n = t2.length();
    int[][] dp = new int[m + 1][n + 1];        // 第 0 行/列表示空串，天然为 0
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (t1.charAt(i - 1) == t2.charAt(j - 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];
}

1035. 不相交的线换个说法（连线不能交叉）但转移完全一致——本质就是 LCS。

115. 不同的子序列

问 s 的子序列中 t 出现了几次（比如 s="babgbag", t="bag" 答案 5）。dp[i][j] 表示"s 的前 i 个字符中凑出 t 的前 j 个字符的方案数"：

• s[i-1] != t[j-1]：s 第 i 个字符没法用，只能丢弃 → dp[i][j] = dp[i-1][j]；
• 相等：用它（dp[i-1][j-1]）+ 不用它（dp[i-1][j]）两种选择相加。

初始化 dp[i][0] = 1：空串是任何串的子序列，且只有一种（全删）。

public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    long[][] dp = new long[m + 1][n + 1];      // 方案数会爆 int，用 long
    for (int i = 0; i <= m; i++) dp[i][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];           // 默认不用 s[i-1]
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] += dp[i - 1][j - 1];  // 匹配上则累加"用它"的方案
            }
        }
    }
    return (int) dp[m][n];
}

对比 1143 和 115 的转移方向：求长度用 max，求方案数用求和，双串 DP 的骨架不变。

三、编辑距离（72）：增删改三操作详细推导

问把 word1 变成 word2 最少需要几次操作（插入/删除/替换一个字符）。这是双串 DP 的巅峰题，我们把递推完整推一遍。

状态定义：dp[i][j] = 把 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。

先推初始化（一边为空的边界）：

• dp[i][0] = i：word2 是空的，word1 只能删 i 个字符；
• dp[0][j] = j：word1 是空的，只能插入 j 个字符。

再推一般转移：比较 w1[i-1] 和 w2[j-1]：

1. 相等：这个字符不用动，问题规模同时缩小——dp[i][j] = dp[i-1][j-1]。

2. 不等：三种操作各对应一个来源，取最小：

   操作	动作	来源状态
   删除	删掉 w1 的第 i 个字符	dp[i-1][j] + 1
   插入	在 w1 末尾补上 w2 的第 j 个字符（等价于 w2 少一个要凑）	dp[i][j-1] + 1
   替换	把 w1 的第 i 个字符改成 w2 的第 j 个字符	dp[i-1][j-1] + 1

   即 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

用 horse → ros 手推一小段验证：dp[3][2]（hor→ro）应该为 1（删除 e），dp[5][3]（horse→ros）为 3（替换 h→r、删 r、删 e），逻辑自洽。

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;   // 全删
    for (int j = 0; j <= n; j++) dp[0][j] = j;   // 全插
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];     // 字符相同，不花操作
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1],          // 替换
                          Math.min(dp[i - 1][j], dp[i][j - 1]) // 删除/插入
                        ) + 1;
            }
        }
    }
    return dp[m][n];
}

顺带一提 583. 两个字符串的删除操作：只允许删除，转移退化为 max(dp[i-1][j], dp[i][j-1]) + 1，是编辑距离的降级热身。

四、区间 DP 入门：回文子串与最长回文子序列

647. 回文子串

统计字符串里回文子串的个数。这次状态的定义对象是一段区间而不是前缀：dp[i][j] 表示 [i, j] 是否为回文。

转移：s[i] == s[j] 时还要看内部——j - i 小于等于 2（"a"、"aa"、"aba"）直接是回文；否则依赖 dp[i+1][j-1]。

遍历方向为什么从下往上？ 因为 dp[i][j] 依赖左下方 dp[i+1][j-1]（i 更大、j 更小）。要保证算 dp[i][j] 时它已就绪，i 必须从大到小、j 从小到大遍历。这也是区间 DP 的通用法则：依赖方向决定遍历方向。

依赖关系（表格中 → 表示"我要用它"）：
dp[i][j]  →  dp[i+1][j-1]   （左下角）
因此行 i 要在行 i+1 之后计算 → i 从 n-1 倒着枚举到 0

public int countSubstrings(String s) {
    int n = s.length(), ans = 0;
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {         // 行倒序：先算 i+1 行
        for (int j = i; j < n; j++) {          // 列从 i 开始，只填上半三角
            if (s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                ans++;
            }
        }
    }
    return ans;
}

516. 最长回文子序列

子序列版本允许跳着取字符，转移改成：

• s[i] == s[j]：两端配对，dp[i][j] = dp[i+1][j-1] + 2；
• 不等：丢一头取较大，max(dp[i+1][j], dp[i][j-1])。

初始化对角线 dp[i][i] = 1（单字符自成回文），答案 dp[0][n-1]。注意这里布尔判定变成了计数求长度，但区间缩小的骨架完全一致。

五、复杂度与易错点

复杂度：300 解法一 O(n²)，解法二 O(nlogn)；1143/115/72 均 O(m·n) 时间与空间（可滚动优化到一维）；647/516 均 O(n²)。

易错点清单：

1. 300 的 dp[i] 定义必须带"以 i 结尾"，答案取 max(dp) 而不是 dp[n-1]。
2. 二分解法里 tails 只是长度可靠，误用它输出具体序列会出错。
3. 双串 DP 统一用 charAt(i-1) 对齐"前 i 个字符"的语义，下标差一最常见。
4. 115 忘了 dp[i][0] = 1 或用 int 累加导致溢出。
5. 72 的插入操作来源写错：是在 w1 侧补字符，对应 dp[i][j-1] 而非 dp[i-1][j]。
6. 区间 DP 遍历方向反了（i 从小到大），会引用尚未计算的 dp[i+1][j-1]。

六、LeetCode 题目清单

参考

• 代码随想录 · 子序列与编辑距离