序列&编辑距离：从基础递推到跨表匹配

哈喽，大家好呀，我是蔚蓝🥰，今天我们来深入聊聊动态规划里的「硬骨头」：序列与编辑距离系列。

不知道大家在刷 LeetCode 或者准备考研机试的时候，有没有被这几种题目绕晕过：这道题到底要不要连续？两个子序列怎么比？编辑距离那三个操作到底是啥意思？

其实，序列类 DP 就像是在玩一场「接龙游戏」。每一个状态 dp[i] 或 dp[i][j] 都是在记录一段路走完后的「当前最佳成绩」。只要理清了它是如何从之前的「小成绩」累加过来的，你会发现大厂高频题也就那么回事。

0. 序列问题的灵魂三问

在动手写代码之前，我通常会先问自己三个问题：

第一问：我的状态代表什么「快照」？

序列问题的核心通常在 「结尾」。

  • 线性序列：通常定义为 dp[i] 表示以第 i 个元素结尾的子序列性质（比如 LIS）。
  • 双序列：通常定义为 dp[i][j] 表示第一个序列前 i 个字符和第二个序列前 j 个字符的匹配情况。
  • 区间序列：通常定义为 dp[i][j] 表示区间 [i, j] 内的子串性质（比如回文）。

第二问：断了怎么办？（连续 vs 不连续）

这是最容易掉坑的地方。

  • 连续（子数组/子串）：如果当前字符不匹配，缘分就尽了，状态直接重置为 0 或者 false。
  • 不连续（子序列）：即使当前不匹配，之前的积累还在，你可以选择跳过当前字符，从 dp[i-1] 继承大统。

第三问：我该往哪看？（遍历顺序）

  • 从前往后：最常见的 LIS 和 LCS。
  • 从下往上，从左往右：这是回文类区间 DP 的专属指纹，因为 dp[i][j] 往往依赖它的「内心数据」 dp[i+1][j-1]。

接下来的这部分，是我在备考期间整理的最全「序列与编辑距离」Java 笔记。里面包含了从最基础的长递增子序列到最复杂的编辑距离，每一道题的定义、方程、避坑点和完整源码都在这里了。

大家可以直接收藏，这套模板拿走就能用！

序列与编辑距离全集

1. 最长增子序列 (LIS)

  • 300. 最长递增子序列
  • 题目描述：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
  • dp 数组定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
  • 状态转移方程：dp[i] = max(dp[j] + 1)，其中 0 <= j < i 且 nums[j] < nums[i]。
  • 注意点：
    1. 初始化：每一个 dp[i] 至少为 1（自身作为一个序列）。
    2. 遍历顺序：两层 for 循环，外层 i 从左到右，内层 j 遍历 0 到 i-1。
    3. 最终结果：结果是整个 dp 数组中的最大值，而不是最后一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

2. 最长连续递增序列 (LCIS)

  • 674. 最长连续递增序列
  • 题目描述：给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。
  • dp 数组定义：dp[i] 表示以 nums[i] 结尾的最长连续递增子序列的长度。
  • 状态转移方程：若 nums[i] > nums[i-1]，则 dp[i] = dp[i-1] + 1；否则 dp[i] = 1。
  • 注意点：
    1. 连续性：因为要求连续，所以只需要比较前一个元素 i-1。
    2. 复杂度：时间复杂度 $O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int res = 1, count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) count++;
            else count = 1;
            res = Math.max(res, count);
        }
        return res;
    }
}

3. 最长重复子数组

  • 718. 最长重复子数组
  • 题目描述：给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组（连续）的长度。
  • dp 数组定义：dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度。
  • 状态转移方程：若 nums1[i-1] == nums2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = 0。
  • 注意点：
    1. 数组长度：通常开 [m+1][n+1]，方便处理空前缀的情况。
    2. 归零逻辑：子数组要求连续，如果不相等，公共前缀长度必须重置为 0。
    3. 最终结果：结果是整个二维数组中的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }
}

4. 最长公共子序列 (LCS)

  • 1143. 最长公共子序列
  • 题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列（可不连续）的长度。
  • dp 数组定义：dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度。
  • 状态转移方程：
    • 若 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
    • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  • 注意点：
    1. 不要求连续：如果不匹配，可以从删除 text1 末尾或删除 text2 末尾的状态中取最大值（这就是它与“子数组”的区别）。
    2. 最终结果：结果在右下角 dp[m][n]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.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];
    }
}

5. 最大子数组和

  • 53. 最大子数组和
  • 题目描述：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
  • dp 数组定义：dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。
  • 状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])。
  • 注意点：
    1. 决策意图：是把当前的 nums[i] 加入到之前的子序列中，还是从当前位置自立门户。
    2. 空间优化：因为 dp[i] 只依赖 dp[i-1]，可以用一个变量替代数组。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

6. 判断子序列

  • 392. 判断子序列

  • 题目描述：给定字符串 s 和 t ，判断 s 是否为 t 的子序列（不要求连续）。

  • dp 数组定义：dp[i][j] 表示 s[0..i-1] 和 t[0..j-1] 的最长公共子序列长度。

  • 状态转移方程：同 LCS。

  • 注意点：

    1. 最终判断：如果 dp[m][n] == s.length()，则说明 s 是 t 的子序列。
    2. 现实做法：面试中首选双指针，$O(n)$ 时间 $O(1)$ 空间。
1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) i++;
            j++;
        }
        return i == s.length();
    }
}

7. 不同的子序列

  • 115. 不同的子序列

  • 题目描述：给你两个字符串 s 和 t ，统计在 s 的子序列中 t 出现的次数。

  • dp 数组 definition：dp[i][j] 表示 s[0..i-1] 的子序列中 t[0..j-1] 出现的个数。

  • 状态转移方程：

    • 若 s[i-1] == t[j-1]：dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (用当前字符匹配 + 不用当前字符匹配)
    • 否则：dp[i][j] = dp[i-1][j] (只能选择不用当前字符匹配)

  • 注意点：

    1. 初始化：dp[i][0] = 1（空串是任何串的子序列且只有一种方案），dp[0][j] = 0 (j>0)。
    2. 数据规模：结果可能很大，Java 中通常用 int 即可，有些特殊题可能需要 long 或对结果取模。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        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++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[m][n];
    }
}

8. 两个字符串的删除操作

  • 583. 两个字符串的删除操作

  • 题目描述：给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。

  • dp 数组定义：dp[i][j] 表示使 word1[0..i-1] 和 word2[0..j-1] 相等所需的最小删除步数。

  • 状态转移方程：

    • 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
    • 否则：dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)

  • 注意点：

    1. 初始化：dp[i][0] = i（word2 为空，删光 word1），dp[0][j] = j。
    2. 转化思路：最小步数 = word1.length() + word2.length() - 2 * LCS。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    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 = 1; i <= m; i++) dp[i][0] = i;
        for (int j = 1; 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], dp[i][j-1]) + 1;
            }
        }
        return dp[m][n];
    }
}

9. 编辑距离

  • 72. 编辑距离

  • 题目描述：给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数（插入、删除、替换）。

  • dp 数组定义：dp[i][j] 表示将 word1[0..i-1] 转换成 word2[0..j-1] 所使用的最少操作数。

  • 状态转移方程：

    • 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
    • 否则：dp[i][j] = min(dp[i-1][j-1] + 1, dp[i-1][j] + 1, dp[i][j-1] + 1) (分别是：替换、删除、插入)

  • 注意点：

    1. 插入等价性：对 word1 插入 ≡ 对 word2 删除。
    2. 初始化：dp[i][0] = i, dp[0][j] = j。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    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 = 1; i <= m; i++) dp[i][0] = i;
        for (int j = 1; 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];
    }
}

10. 回文子串 (计数)

  • 647. 回文子串

  • 题目描述：给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。

  • dp 数组定义：dp[i][j] 表示区间 [i, j] 的子串是否为回文。

  • 状态转移方程：若 s[i] == s[j] 且 (j - i <= 1 或 dp[i+1][j-1])，则 dp[i][j] = true。

  • 注意点：

    1. 遍历顺序：这是区间 DP，dp[i][j] 依赖左下方的 dp[i+1][j-1]，所以 i 必须从下到上，j 从左到右。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int countSubstrings(String s) {
        int n = s.length(), res = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) { // 下往上
            for (int j = i; j < n; j++) { // 左往右
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    res++;
                }
            }
        }
        return res;
    }
}

11. 最长回文子序列

  • 516. 最长回文子序列
  • 题目描述：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度（子序列可不连续）。
  • dp 数组定义：dp[i][j] 表示区间 [i, j] 内最长回文子序列的长度。
  • 状态转移方程：
    • 若 s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2
    • 否则：dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  • 注意点：
    1. 初始化：dp[i][i] = 1。
    2. 遍历顺序：同样是区间 DP，i 从下到上，j 从左到右。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
}

12. 最长回文子数组 (最长回文子串)

  • 5. 最长回文子串
  • 题目描述：给你一个字符串 s，找到 s 中最长的回文子串。
  • dp 数组定义：dp[i][j] 表示区间 [i, j] 的子串是否为回文（boolean 类型）。
  • 状态转移方程：
    • 若 s[i] == s[j]：
      • 若 j - i <= 1（长度为 1 或 2）：dp[i][j] = true
      • 否则：dp[i][j] = dp[i+1][j-1]（取决于中间部分是否为回文）
    • 否则：dp[i][j] = false
  • 注意点：
    1. 连续性：子数组/子串必须连续，因此不能像“子序列”那样在不相等时通过 max 继承。
    2. 全局最值：dp 数组存储的是合法性，最长长度需要在 dp[i][j] == true 时通过 j - i + 1 动态更新。
    3. 遍历顺序：区间 DP 经典顺序，i 从下到上，j 从左到右。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        int maxLen = 1;
        int begin = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = true;

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                }
        
                if (dp[i][j] && (j - i + 1) > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

碎碎念

其实写代码就像走路，最怕的就是一边走一边看导航（死记硬背方程），结果掉进坑里（理解错连续性）都不知道。

下次遇到序列问题，先别急着写代码。拿张纸画一个格子，像玩消消乐一样推演一下状态。当你能看清每一个格子里的数字是怎么滚出来的时候，那代码写起来，真的就像呼吸一样自然。

希望这份全集能帮你彻底刷通序列 DP！下次见啦~