跳至主要內容

最长公共子序列——LCS状态推导与打印路径

老张2026/4/30大约 9 分钟

最长公共子序列——LCS状态推导与打印路径

适读人群：Java后端工程师、序列DP学习者 | 阅读时长：约22分钟 | 难度：Medium

开篇故事

LCS是我在读大学算法课时第一次接触的"经典DP"，课上老师讲了足足一节课，我听完觉得自己懂了，课后自己写，写了两个小时才勉强通过所有测试用例。

后来工作了，差分文件比对、版本控制的diff算法，本质上都是LCS的变体。Git的diff命令背后就有类似的思想。所以这不只是一道算法题，它在实际工程里是真实存在的。

到了面试场，LCS更是高频考题。有一次我面试一家大厂，面试官直接问："你能手写LCS的DP并且打印出具体的公共子序列吗？"求长度不难，但打印具体路径，很多人当场卡住了。

路径回溯这个技巧，是DP的另一个重要维度。求最优值是DP的主业，而很多题目还要求你给出达到最优值的具体方案，这需要在DP的过程中记录额外信息，回溯时才能重建路径。今天把这两部分都讲透。

一、题目解析

题号：LeetCode 1143. Longest Common Subsequence

题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。

一个字符串的子序列是指：从字符串中删去某些字符（也可以不删）而不改变其余字符顺序所形成的新字符串。

示例：

  • 输入：text1 = "abcde"，text2 = "ace"，输出：3（"ace"）
  • 输入：text1 = "abc"，text2 = "abc"，输出：3
  • 输入：text1 = "abc"，text2 = "def"，输出：0

核心考点：二维DP，字符匹配的分支处理，路径回溯，空间压缩

二、DP思路推导

2.1 为什么是二维DP

LCS处理的是两个字符串，自然地就需要用两个维度来描述问题的状态。

一个字符串的下标 i，代表"考虑了前 i 个字符"。两个字符串就需要 (i, j) 二元组来描述当前处理到的位置。

2.2 状态定义

定义 dp[i][j] = text1前i个字符与text2前j个字符的最长公共子序列长度

即：dp[i][j] = LCS(text1[0..i-1], text2[0..j-1])

这里使用 1-indexed，dp[0][] 和 dp[][0] 表示某个字符串为空时的情况，LCS长度自然为0，方便边界处理。

2.3 状态转移方程推导

最关键的分析：在 text1[0..i-1] 和 text2[0..j-1] 的LCS中，关注最后一个位置 i 和 j 的字符是否相等：

情况一：text1[i-1] == text2[j-1]（字符相等）

两个字符串的最后一个字符匹配！那么这个字符一定在LCS里，LCS = LCS(text1[0..i-2], text2[0..j-2]) + 1

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

情况二：text1[i-1] != text2[j-1]（字符不等）

最后两个字符不能同时出现在LCS里。两种选择：

  • 不考虑 text1[i-1]：LCS = LCS(text1[0..i-2], text2[0..j-1])，即 dp[i-1][j]
  • 不考虑 text2[j-1]：LCS = LCS(text1[0..i-1], text2[0..j-2])，即 dp[i][j-1]

取两者最大值：

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

完整转移方程：

       dp[i-1][j-1] + 1           if text1[i-1] == text2[j-1]
dp[i][j] = 
       max(dp[i-1][j], dp[i][j-1])  if text1[i-1] != text2[j-1]

2.4 边界条件

  • dp[0][j] = 0：text1为空，LCS为0
  • dp[i][0] = 0：text2为空，LCS为0

Java中 int 数组默认初始化为0，所以不需要额外赋值。

2.5 状态转移示意（完整DP表）

text1 = "abcde"，text2 = "ace"

     ""  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[5][3] = 3

三、解法一：基础二维DP

public class LongestCommonSubsequence {
    
    /**
     * 1143. 最长公共子序列 - 基础二维DP
     * 时间复杂度：O(m * n)
     * 空间复杂度：O(m * n)
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // dp[i][j] = text1前i个字符与text2前j个字符的LCS长度
        int[][] dp = new int[m + 1][n + 1];
        
        // 边界：dp[0][*] = 0，dp[*][0] = 0，Java默认初始化已满足
        
        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];
    }
}

Mermaid状态转移图：

四、解法二：打印具体的LCS路径

只求长度不难，但打印具体路径需要两个步骤：

  1. 正向DP：填充 dp 表，同时记录每个状态的"来源"
  2. 反向回溯：从 dp[m][n] 开始，根据来源标记倒推路径，收集字符

方式A：保存来源标记

/**
 * 打印LCS路径 - 方式A：保存来源标记
 */
public String findLCS(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    // 记录每个位置的来源：0=对角线, 1=上方, 2=左方
    int[][] from = 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;
                from[i][j] = 0;  // 来自左上角（字符匹配）
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j];
                from[i][j] = 1;  // 来自上方
            } else {
                dp[i][j] = dp[i][j - 1];
                from[i][j] = 2;  // 来自左方
            }
        }
    }
    
    // 反向回溯
    StringBuilder sb = new StringBuilder();
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (from[i][j] == 0) {
            // 字符匹配，加入LCS
            sb.append(text1.charAt(i - 1));
            i--;
            j--;
        } else if (from[i][j] == 1) {
            i--;  // 来自上方，text1去掉最后一个字符
        } else {
            j--;  // 来自左方，text2去掉最后一个字符
        }
    }
    
    return sb.reverse().toString();  // 反转，因为是倒序添加的
}

方式B：直接根据dp值回溯（不需要额外空间）

/**
 * 打印LCS路径 - 方式B：根据dp值直接回溯
 * 不需要额外的from数组
 */
public String findLCSByDP(String text1, String text2) {
    int m = text1.length();
    int 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]);
            }
        }
    }
    
    // 根据dp值判断来源，反向回溯
    StringBuilder sb = new StringBuilder();
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            sb.append(text1.charAt(i - 1));
            i--;
            j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return sb.reverse().toString();
}

路径回溯的图示（以"abcde"和"ace"为例）：

回溯路径（从dp[5][3]开始）：

dp[5][3]=3: text1[4]='e' == text2[2]='e'，添加'e'，→ dp[4][2]
dp[4][2]=2: text1[3]='d' != text2[1]='c'，dp[3][2]=2 >= dp[4][1]=1，→ dp[3][2]
dp[3][2]=2: text1[2]='c' == text2[1]='c'，添加'c'，→ dp[2][1]
dp[2][1]=1: text1[1]='b' != text2[0]='a'，dp[1][1]=1 >= dp[2][0]=0，→ dp[1][1]
dp[1][1]=1: text1[0]='a' == text2[0]='a'，添加'a'，→ dp[0][0]

收集到：e, c, a，反转得 ace ✓

五、解法三：空间压缩（一维滚动数组）

二维DP可以压缩到一维，但LCS的压缩比背包稍复杂，因为需要用到 dp[i-1][j-1]（左上角的值），在滚动时会被覆盖。

/**
 * 1143. LCS - 一维空间压缩
 * 时间复杂度：O(m * n)
 * 空间复杂度：O(min(m, n))
 */
public int longestCommonSubsequenceOptimized(String text1, String text2) {
    // 让text2是较短的那个，节省空间
    if (text1.length() < text2.length()) {
        return longestCommonSubsequenceOptimized(text2, text1);
    }
    
    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];  // 保存dp[i-1][j]，下一轮作为dp[i-1][j-1]
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[j] = prev + 1;  // prev是dp[i-1][j-1]
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);  // max(dp[i-1][j], dp[i][j-1])
            }
            prev = temp;  // 更新prev为本轮的dp[i-1][j]，下次迭代用作dp[i-1][j-1]
        }
    }
    
    return dp[n];
}

空间压缩的关键技巧：用一个变量 prev 在内层循环中保存"即将被覆盖的 dp[i-1][j-1]"，在更新 dp[j] 之前先把旧值存起来。

六、举一反三

LCS的变体与相关题目：

  1. LeetCode 72. 编辑距离：LCS思想的扩展，增删改三种操作（下篇详讲）
  2. LeetCode 516. 最长回文子序列：s和reverse(s)的LCS
  3. LeetCode 718. 最长重复子数组：子串版（连续），区别于子序列版（非连续）
  4. LeetCode 1458. 两个子序列的最大点积：LCS计数的变体

LCS通用框架：

// 对于两个序列s1, s2的二维DP
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (s1[i-1] == s2[j-1]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        } else {
            dp[i][j] = max/min(dp[i-1][j], dp[i][j-1]);  // 根据题目选max还是min
        }
    }
}

七、踩坑实录

坑一：1-indexed还是0-indexed混用

我建议LCS始终用1-indexed（dp大小为m+1, n+1），这样dp[0][]和dp[][0]天然是0，不需要额外的边界初始化，也不容易混淆字符串的索引。如果用0-indexed，边界处理容易出错。

坑二：打印路径时字符顺序反了

回溯是从右下角往左上角走，添加字符的顺序是倒序的。最后一定要用 reverse() 反转结果。很多人写完路径回溯，直接返回 sb.toString()，字符顺序是反的。

坑三：空间压缩时prev变量丢失

一维滚动时，内层循环每次更新 dp[j] 之前，必须先保存旧的 dp[j]（也就是 dp[i-1][j]），因为它在下一次迭代中要作为 dp[i-1][j-1] 使用。如果忘记保存，prev 的值就不对，LCS计算就出错了。

坑四：字符匹配时用了错误的前置状态

字符匹配时，转移方程是 dp[i][j] = dp[i-1][j-1] + 1，而不是 dp[i-1][j] + 1 或 dp[i][j-1] + 1。有人在写代码时随手写成了max的版本，忘记了字符匹配时应该走对角线。

八、总结

LCS是二维DP的经典入门题，核心思路：

  • 字符匹配时：走对角线，dp[i][j] = dp[i-1][j-1] + 1
  • 字符不匹配：取两个方向的最大值，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

打印路径：保存dp值，反向回溯，遇到字符匹配就收集字符，最后反转。

空间压缩：一维滚动，用prev变量保存左上角值，避免被覆盖。

解法时间空间
二维DPO(m×n)O(m×n)
一维压缩O(m×n)O(min(m,n))
编辑此页
最近更新:
贡献者: xiaozhangge