数据结构与算法 / 系统课时

最长公共子序列

最长公共子序列

给定两个序列,我们将用二维动态规划求出“允许跳过元素、但保持相对顺序”的最长匹配长度,再沿状态表回溯出一个实际的最长公共子序列。通过 Java 17 示例,你将掌握状态转移、路径重建与结果验证,并理解为什么最优解可能不唯一。

学习目标

  • 准确定义最长公共子序列的状态、边界与转移规则。
  • 使用二维动态规划计算 LCS 长度并分析时间、空间复杂度。
  • 根据状态表重建一个具体解,理解多解现象并验证结果。

问题定义与状态设计

最长公共子序列(Longest Common Subsequence,LCS)允许跳过元素,但要求选中元素的相对顺序保持不变。它与最长公共子串不同:子串要求匹配元素在原序列中连续出现,而子序列不要求连续。

例如,ABCBDAB 与 BDCABA 的最长公共子序列长度为 4,一个具体解是 BCBA。两个字符串中都能按顺序找到 B、C、B、A,即使这些字符之间存在未选中的字符,也不影响结果。

设第一个字符串 first 的长度为 m,第二个字符串 second 的长度为 n。定义 dp[i][j] 表示 first 的前 i 个字符与 second 的前 j 个字符的最长公共子序列长度。

状态表大小为 (m + 1) × (n + 1),多出的首行和首列用于表示空前缀。任一前缀为空时,不可能存在非空公共子序列,因此边界为:

dp[0][j]=dp[i][0]=0dp[0][j] = dp[i][0] = 0

这里的 i、j 表示前缀长度,而不是字符下标。例如,dp[3][2] 比较的是 first 的前三个字符与 second 的前两个字符。这个区别决定了后续字符访问必须使用 i - 1 和 j - 1。

状态转移与复杂度

对于 i ≥ 1、j ≥ 1,比较 first.charAt(i - 1) 与 second.charAt(j - 1),根据末尾字符是否相同选择不同的转移方式。

当两个当前字符相同时,存在一个最优解包含这两个末尾字符,可以在两个更短前缀的最长公共子序列后追加该字符:

dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i - 1][j - 1] + 1

当两个当前字符不同时,公共子序列不能同时包含这两个末尾字符。因此,至少需要舍弃其中一个,分别考察忽略第一个字符串末尾字符与忽略第二个字符串末尾字符的结果:

dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])dp[i][j] = \max(dp[i - 1][j], dp[i][j - 1])

例如,ABC 与 BDC 的末尾字符均为 C,因此最后一个状态由左上角状态加 1 得到,最终 LCS 为 BC,长度为 2。

填表时按 i = 1 到 m、j = 1 到 n 的顺序逐行计算。每个状态依赖的上方、左方和左上方状态都已经完成,因此不需要递归或重复搜索。

状态表包含 mn 个需要计算的非边界状态,每个状态只需常数次比较和赋值,所以时间复杂度为 O(mn)。完整二维表占用 O(mn) 空间;如果只要求长度,可以使用滚动数组将空间压缩为 O(min(m,n)),但需要重建具体序列时,保留完整状态表最直观。

状态表与路径回溯

填表结束后,dp[m][n] 就是最长公共子序列的长度。但这个数值并不直接告诉我们选择了哪些字符,因此还需要沿状态转移的来源反向追踪。

以 ABCBDAB 和 BDCABA 为例,完整状态表有 8 行、7 列,右下角的值为 4。回溯从 (7, 6) 开始,按照以下规则移动:

  1. 如果两个当前字符相同,将该字符加入结果,并同时执行 i--、j--,移动到左上角。
  2. 如果两个当前字符不同,比较 dp[i - 1][j] 与 dp[i][j - 1],移动到值较大的上方或左方状态。
  3. 如果上方与左方的值相等,可以任选一个方向;本例固定优先向上,保证程序每次运行得到相同结果。
  4. 当 i == 0 或 j == 0 时停止,反转已收集的字符,即得到一个最长公共子序列。

最长公共子序列的二维状态表与回溯路径

在图示回溯中,起点 (7, 6) 的两个当前字符不同,上方与左方的状态值同为 4,所以先向上移动。随后遇到匹配字符 A,走向左上角;继续回溯,依次收集 B、C、B。

由于回溯方向是从序列末尾走向开头,收集结果为 ABCB,反转后得到 BCBA。如果在平局时改为优先向左,可能得到不同的最优子序列,但最终长度仍然是 4。

Java 实现与运行验证

实现时先按行填满状态表,再单独执行回溯。比较字符时必须使用 first.charAt(i - 1) 与 second.charAt(j - 1),因为状态下标包含空前缀,而字符串下标从 0 开始。

回溯过程中使用 StringBuilder 收集字符,结束后调用 reverse(),避免反复向字符串开头插入字符。下面保留完整状态表,方便核对每个状态的计算结果。

将以下代码保存为 LcsDemo.java,使用 Java 17 或更新版本运行:

java
import java.util.Arrays;

public class LcsDemo {

    public static void main(String[] args) {
        String first = "ABCBDAB";
        String second = "BDCABA";

        Result result = solve(first, second);

        System.out.println("第一个序列: " + first);
        System.out.println("第二个序列: " + second);
        System.out.println("最长长度: " + result.length());
        System.out.println("一个最长公共子序列: " + result.sequence());
        System.out.println("状态表:");
        for (int[] row : result.table()) {
            System.out.println(Arrays.toString(row));
        }
    }

    static Result solve(String first, String second) {
        int m = first.length();
        int n = second.length();
        int[][] dp = new int[m + 1][n + 1];

        // 首行和首列默认是 0,表示空前缀的 LCS 长度。
        // 按前缀长度递增填表,确保依赖状态已经计算完成。
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (first.charAt(i - 1) == second.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]);
                }
            }
        }

        // 从右下角回溯,平局时优先向上移动。
        StringBuilder reversed = new StringBuilder();
        int i = m;
        int j = n;

        while (i > 0 && j > 0) {
            if (first.charAt(i - 1) == second.charAt(j - 1)) {
                reversed.append(first.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        // 回溯顺序与原序列相反,返回前恢复正向顺序。
        return new Result(dp[m][n], reversed.reverse().toString(), dp);
    }

    record Result(int length, String sequence, int[][] table) {
    }
}

打开终端,进入 LcsDemo.java 所在目录,执行编译与运行命令:

bash
javac LcsDemo.java
java LcsDemo

预期输出:

text
第一个序列: ABCBDAB
第二个序列: BDCABA
最长长度: 4
一个最长公共子序列: BCBA
状态表:
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1]
[0, 1, 1, 1, 1, 2, 2]
[0, 1, 1, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 3, 3]
[0, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 3, 3, 4]
[0, 1, 2, 2, 3, 4, 4]

输出中的状态表与图示一致,dp[7][6] 为 4,重建出的 BCBA 长度也是 4。验证一个结果是否正确时,除了检查长度,还应检查结果能否分别作为两个输入字符串的子序列出现。

例如,BCBA 在第一个字符串中可对应位置 2、3、4、6,在第二个字符串中可对应位置 1、3、5、6,这里的位置从 1 开始计数。两组位置都严格递增,因此满足子序列的顺序约束。

常见错误与边界验证

最常见的下标错误是把 dp[i][j] 直接对应到 charAt(i) 和 charAt(j)。这样不仅跳过首字符,还会在 i == m 或 j == n 时发生越界。正确写法始终是 charAt(i - 1) 与 charAt(j - 1)。

另一个错误是只返回 dp[m][n],却声称已经得到具体子序列。长度计算与路径重建是两个不同步骤。若需要输出实际字符,必须提供足够的回溯信息;完整状态表是最容易实现和检查的方案。

还需要注意以下边界:

  • 任一输入为空字符串时,LCS 长度为 0,重建结果为空字符串;当前实现可以直接处理。
  • 两个字符串没有共同字符时,最终长度为 0,回溯不会收集到任何字符。
  • 存在多个最优解时,不应只用某个固定的答案字符串判断程序是否正确,而应同时验证长度和子序列合法性。
  • 本示例使用 Java 的 char 进行比较,适合普通英文字符;若需要按 Unicode 码点处理包含补充字符的文本,应改用码点序列,而不是直接按 UTF-16 代码单元匹配。

可以用下面两个练习检查是否真正掌握了状态设计和回溯过程:

  1. 将输入修改为 AGGTAB 与 GXTXAYB,验证 LCS 长度为 4,并检查重建结果 GTAB 是否按顺序出现在两个字符串中。
  2. 把回溯条件 dp[i - 1][j] >= dp[i][j - 1] 改成 dp[i - 1][j] > dp[i][j - 1],让平局时优先向左移动。比较两次得到的字符串,并确认它们的长度都等于 dp[m][n]。

LCS 的二维状态由两个前缀共同确定:字符相同取左上角加一,字符不同取上方和左方的较大值。完整状态表既给出最优长度,也记录了足以重建具体解的状态信息;理解填表方向与回溯方向的区别,就能避免大多数实现错误。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

最长公共子序列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通