最长公共子序列为何能解决十几类LeetCode问题从字符串相似度到DNA比对的动态规划精髓

每次你在终端输入 git diff，后台都在运行一个你可能刷过无数次的算法题——最长公共子序列。这不是巧合，而是计算机科学中最优雅的算法之一在实际工程中的自然落地。从版本控制到生物信息学，从拼写检查到数据压缩，LCS 找到了两个序列之间"最相似的部分"，而这个看似简单的问题背后，隐藏着动态规划的精髓。

一个问题引发的算法革命

假设有两个字符串 text1 = "abcde" 和 text2 = "ace"，它们的最长公共子序列是 "ace"。注意，子序列不要求连续，只要保持相对顺序即可。这个问题的暴力解法需要枚举其中一个字符串的所有子序列（共 $2^n$ 个），然后在另一个字符串中查找——当字符串长度达到 100 时，这个数字已经超过了宇宙中原子的总数。

1970 年代，贝尔实验室的研究员们面临一个实际问题：如何在 Unix 系统中高效地比较两个文件的差异。这个需求直接催生了 diff 命令，而其核心算法正是 LCS。Doug McIlroy 和 James Hunt 在 1976 年发表的论文中，不仅给出了高效的实现方案，还开启了一个持续至今的研究方向——序列相似性度量。

LCS 问题的正式定义是：给定两个序列 $X = \langle x_1, x_2, ..., x_m \rangle$ 和 $Y = \langle y_1, y_2, ..., y_n \rangle$，找出它们最长的公共子序列 $Z$。这里的"公共"意味着 $Z$ 同时是 $X$ 和 $Y$ 的子序列。

动态规划的核心洞察

暴力解法之所以低效，是因为它重复计算了大量重叠子问题。考虑字符串 "ABCD" 和 "ACBD"：当我们比较以 "A" 开头的子序列时，后续的 "BCD" 与 "CBD" 的比较会被重复执行多次。

动态规划的第一个关键洞察是前缀分解：如果知道了所有前缀对的 LCS 长度，就能推导出更长前缀的答案。设 $dp[i][j]$ 表示 $X$ 的前 $i$ 个字符与 $Y$ 的前 $j$ 个字符的 LCS 长度，那么整个问题的解就是 $dp[m][n]$。

第二个关键洞察是最优子结构：如果 $x_i = y_j$，那么这两个字符一定在某个最长公共子序列中匹配。为什么？假设存在一个 LCS 不匹配这两个相同的字符，我们可以把它们加到这个 LCS 中，得到一个更长的公共子序列——矛盾。因此，当末尾字符相同时，问题规模缩减为 $dp[i-1][j-1]$。

如果 $x_i \neq y_j$，那么这两个字符不可能同时出现在 LCS 中。要么 $x_i$ 不在 LCS 中（问题变成 $dp[i-1][j]$），要么 $y_j$ 不在 LCS 中（问题变成 $dp[i][j-1]$）。我们选择这两种情况中更优的那个。

综上，状态转移方程为：

$$ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } x_i = y_j \\ \max(dp[i-1][j], dp[i][j-1]) & \text{if } x_i \neq y_j \end{cases} $$

边界条件：$dp[0][j] = dp[i][0] = 0$（空字符串与任何字符串的 LCS 长度为 0）。

DP 表格的直观理解

以 text1 = "abcde" 和 text2 = "ace" 为例，DP 表格填充过程如下：

        ""  a   c   e
    ""   0   0   0   0
    a    0   1   1   1
    b    0   1   1   1
    c    0   1   2   2
    d    0   1   2   2
    e    0   1   2   3

每一格的计算都有明确的含义：dp[3][2] = 2 表示 "abc" 和 "ac" 的 LCS 长度是 2（即 "ac"）。当 text1[2] = 'c' 与 text2[1] = 'c' 相等时，我们取左上角的值加 1；当不相等时，取上方或左方的较大值。

Git diff 基于 LCS 显示文件差异

图片来源: Wikipedia - Longest Common Subsequence（展示基于 LCS 的文件差异比较）

LeetCode 1143：经典模板题

这是 LCS 最基础的实现题目，要求返回两个字符串的最长公共子序列长度。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度
        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)) {
                    // 字符匹配，LCS 长度加 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];
    }
}

时间复杂度：$O(m \times n)$，需要填充整个 DP 表格。
空间复杂度：$O(m \times n)$，存储整个 DP 表格。

空间优化：从二维到一维

观察状态转移方程，dp[i][j] 只依赖于 dp[i-1][j-1]、dp[i-1][j] 和 dp[i][j-1]。这意味着计算第 $i$ 行时，只需要第 $i-1$ 行的数据。我们可以用两个一维数组交替使用，将空间复杂度降至 $O(\min(m, n))$。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // 确保使用较小的空间
        if (n > m) {
            return longestCommonSubsequence(text2, text1);
        }
        
        int[] prev = new int[n + 1];
        int[] curr = new int[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)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            // 交换数组
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev[n];
    }
}

更进一步，可以只用一个一维数组。关键技巧是用一个变量 prev 保存 dp[i-1][j-1] 的值，因为当我们更新 dp[j] 时，原来的 dp[j] 就是下一轮需要的 dp[i-1][j-1]。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= m; i++) {
            int prev = 0;  // 保存 dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];  // 暂存当前值，作为下一轮的 prev
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        
        return dp[n];
    }
}

如何打印实际的 LCS

有时候不仅需要长度，还需要输出实际的子序列。这需要额外存储"决策信息"——每一步是匹配了字符，还是跳过了某个字符。

方法一是在 DP 时记录方向信息：

public String getLCS(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    
    int[][] dp = new int[m + 1][n + 1];
    // 0: 来自左上角（匹配）, 1: 来自上方, 2: 来自左方
    int[][] path = 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;
                path[i][j] = 0;  // 匹配
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j];
                path[i][j] = 1;  // 来自上方
            } else {
                dp[i][j] = dp[i][j - 1];
                path[i][j] = 2;  // 来自左方
            }
        }
    }
    
    // 回溯构建 LCS
    StringBuilder lcs = new StringBuilder();
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (path[i][j] == 0) {
            lcs.append(text1.charAt(i - 1));
            i--;
            j--;
        } else if (path[i][j] == 1) {
            i--;
        } else {
            j--;
        }
    }
    
    return lcs.reverse().toString();
}

方法二是不存储路径，直接根据 DP 表格回溯。当 text1[i-1] == text2[j-1] 时，必然来自左上角；否则比较上方和左方的值决定方向。

LeetCode 583：两个字符串的删除操作

题目要求找到使两个字符串相等所需的最少删除次数。这个问题的本质是：两个字符串各自删除一些字符后，剩余部分完全相同——这剩余部分正是 LCS。

最少删除次数 = len(text1) - LCS + len(text2) - LCS = len(text1) + len(text2) - 2 * LCS

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= m; i++) {
            int prev = 0;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        
        int lcs = dp[n];
        return m + n - 2 * lcs;
    }
}

LeetCode 718：最长重复子数组

这是 LCS 的一个变种：要求公共部分必须是连续的子数组（子串），而不是子序列。状态转移方程稍有不同：

$$ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } nums1[i-1] = nums2[j-1] \\ 0 & \text{if } nums1[i-1] \neq nums2[j-1] \end{cases} $$

关键区别在于：当字符不匹配时，连续性被打断，dp[i][j] 直接置 0，而不是继承前值。同时，答案不再是 dp[m][n]，而是整个表格中的最大值。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        
        int[] dp = new int[n + 1];
        int maxLen = 0;
        
        for (int i = 1; i <= m; i++) {
            // 必须从右向左遍历，否则会覆盖需要的值
            for (int j = n; j >= 1; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[j]);
                } else {
                    dp[j] = 0;  // 不匹配时重置为 0
                }
            }
        }
        
        return maxLen;
    }
}

注意这里必须从右向左遍历，因为 dp[j] 依赖于 dp[j-1]（上一行的前一个位置）。如果从左向右遍历，会覆盖还没使用的值。

LeetCode 516：最长回文子序列

回文子序列有一个优美的性质：一个字符串的最长回文子序列，等于该字符串与其反转字符串的 LCS。

为什么？设原字符串为 $S$，反转后为 $S'$。如果 $P$ 是 $S$ 的回文子序列，那么 $P$ 也是 $S'$ 的子序列（因为 $P$ 正读反读一样）。因此 $P$ 是 $S$ 和 $S'$ 的公共子序列。反之亦然。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        String reversed = new StringBuilder(s).reverse().toString();
        
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            int prev = 0;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (s.charAt(i - 1) == reversed.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        
        return dp[n];
    }
}

当然，这道题也可以直接用区间 DP 解决，复杂度相同但可能更直观。

LeetCode 1312：让字符串成为回文的最少插入次数

有了 LCS 和回文子序列的知识，这个问题变得非常清晰。最少插入次数等于字符串长度减去最长回文子序列长度——我们需要插入的字符就是那些"配不上对"的字符。

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        String reversed = new StringBuilder(s).reverse().toString();
        
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            int prev = 0;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (s.charAt(i - 1) == reversed.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        
        int lps = dp[n];  // Longest Palindromic Subsequence
        return n - lps;
    }
}

LeetCode 1092：最短公共超序列

题目要求找到能同时包含两个字符串作为子序列的最短字符串。这个问题的解与 LCS 密切相关。

设两个字符串为 $S_1$ 和 $S_2$，长度分别为 $m$ 和 $n$。最短公共超序列的长度为 $m + n - |LCS|$。为什么？LCS 部分只需要出现一次，非 LCS 部分需要全部包含。

构建超序列的方法：从两个字符串的末尾开始，根据 LCS 表格决定如何合并。

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        
        // 构建 DP 表格
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.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 result = new StringBuilder();
        int i = m, j = n;
        
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                // 字符匹配，属于 LCS，只添加一次
                result.append(str1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                // 来自上方，str1 的当前字符不在 LCS 中
                result.append(str1.charAt(i - 1));
                i--;
            } else {
                // 来自左方，str2 的当前字符不在 LCS 中
                result.append(str2.charAt(j - 1));
                j--;
            }
        }
        
        // 处理剩余字符
        while (i > 0) {
            result.append(str1.charAt(i - 1));
            i--;
        }
        while (j > 0) {
            result.append(str2.charAt(j - 1));
            j--;
        }
        
        return result.reverse().toString();
    }
}

LCS 与编辑距离的关系

编辑距离（LeetCode 72）是 LCS 的一个扩展版本。如果只允许插入和删除操作（不允许替换），那么编辑距离与 LCS 的关系是：

$$ \text{EditDistance} = m + n - 2 \times |LCS| $$

解释：将字符串 $A$ 转换为 $B$，需要删除 $A$ 中不在 LCS 中的字符（共 $m - |LCS|$ 个），再插入 $B$ 中不在 LCS 中的字符（共 $n - |LCS|$ 个）。

如果允许替换操作，情况会更复杂，但 LCS 的思想仍然是基础。

真实世界中的应用

Git diff 的核心算法

每次运行 git diff，Git 都在执行某种形式的 LCS 计算。不过，标准 LCS 的 $O(mn)$ 复杂度对于大文件来说仍然太慢。Git 使用的是 Myers 算法（1986 年由 Eugene Myers 提出），时间复杂度为 $O((m+n)D)$，其中 $D$ 是两个文件的差异大小。

对于主要差异较小的文件（这是大多数实际情况），$D$ 远小于 $m$ 和 $n$，因此 Myers 算法比标准 LCS 快得多。

DNA 序列比对

在生物信息学中，LCS 用于比较 DNA、RNA 或蛋白质序列的相似性。两个物种的基因组越相似，它们的 LCS 就越长。不过，实际应用中使用的是带权重的变体（如 Needleman-Wunsch 算法），允许对匹配、错配和空隙赋予不同的分数。

拼写检查与模糊搜索

编辑距离常用于拼写检查器中找到与用户输入最相似的单词。LCS 作为编辑距离的基础，间接支撑了这一应用。

Hirschberg 算法：线性空间的 LCS 构造

前面讨论的空间优化只能求 LCS 长度，不能构造实际的 LCS。1975 年，Dan Hirschberg 提出了一种分治算法，可以在 $O(\min(m, n))$ 空间内构造 LCS，同时保持 $O(mn)$ 时间复杂度。

算法的核心思想是：

计算 $X$ 与 $Y$ 所有前缀的 LCS 长度（正向 DP）
计算 $X$ 与 $Y$ 所有后缀的 LCS 长度（反向 DP）
找到 $Y$ 的最优分割点 $k$，使得正向和反向的 LCS 长度之和最大
递归处理两个子问题

这是一个精妙的分治与动态规划结合的例子，展示了算法设计中"空间换时间"与"分而治之"两种思想的融合。

LCS 相关 LeetCode 题目汇总

题目编号	题目名称	核心技巧
1143	最长公共子序列	基础 LCS
583	两个字符串的删除操作	LCS 长度转换
718	最长重复子数组	连续子序列版本
516	最长回文子序列	LCS + 字符串反转
1312	让字符串成为回文的最少插入次数	LCS + 回文
1092	最短公共超序列	LCS 回溯构造
392	判断子序列	LCS 长度等于短字符串长度
115	不同的子序列	LCS 的计数版本
72	编辑距离	LCS 的扩展（允许替换）

小结

最长公共子序列之所以成为动态规划的经典范例，不仅因为它展示了重叠子问题和最优子结构的核心思想，更因为它有着广泛的实际应用。从 git diff 到 DNA 序列比对，从拼写检查到数据压缩，LCS 的身影无处不在。

掌握 LCS，不仅是刷题的需要，更是理解一类问题——“序列相似性度量”——的起点。在此基础上，编辑距离、序列比对、模糊匹配等问题都会变得迎刃而解。而当你下次在终端输入 git diff 时，你看到的不再是一堆加减号，而是一个运行了几十年的经典算法。

参考文献

Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 15.4.
Hunt, J. W., & McIlroy, M. D. (1976). An Algorithm for Differential File Comparison. Bell Laboratories Computing Science Technical Report #41.
Myers, E. W. (1986). An O(ND) Difference Algorithm and Its Variations. Algorithmica, 1(1-4), 251-266.
Hirschberg, D. S. (1975). A Linear Space Algorithm for Computing Maximal Common Subsequences. Communications of the ACM, 18(6), 341-343.
Bergroth, L., Hakonen, H., & Raita, T. (2000). A Survey of Longest Common Subsequence Algorithms. SPIRE, 39-48.

一个问题引发的算法革命#

动态规划的核心洞察#

DP 表格的直观理解#

LeetCode 1143：经典模板题#

空间优化：从二维到一维#

如何打印实际的 LCS#

LeetCode 583：两个字符串的删除操作#

LeetCode 718：最长重复子数组#

LeetCode 516：最长回文子序列#

LeetCode 1312：让字符串成为回文的最少插入次数#

LeetCode 1092：最短公共超序列#

LCS 与编辑距离的关系#

真实世界中的应用#

Git diff 的核心算法#

DNA 序列比对#

拼写检查与模糊搜索#

Hirschberg 算法：线性空间的 LCS 构造#

LCS 相关 LeetCode 题目汇总#

小结#

更多精彩内容

背包问题为何成为动态规划的基石从01背包到完全背包的完整LeetCode通关指南

字符串匹配算法为何如此重要从KMP到Z函数的线性时间突围

字典树（Trie）：用共享前缀把字符串检索从O(n)降到O(L)

动态规划算法入门：从暴力递归到状态转移的完整思维指南

扫描线算法如何将二维问题降维成一维从天际线到矩形面积的LeetCode完整通关指南