每日算法 — 使用java实现最长公共子序列：动态规划与空间优化

最长公共子序列（Longest Common Subsequence, LCS）是文本比对、版本控制（Git diff）、DNA序列分析等领域的核心算法。给定两个字符串，找出它们最长的公共子序列的长度。与最长公共子串不同，LCS 不要求字符连续，只要求相对顺序一致。本文将用Java实现LCS的动态规划解法，并深入讲解如何将空间复杂度从 O(mn) 优化到 O(min(m, n))。

一、问题定义与示例

输入: text1 = "ABCDE", text2 = "ACE"
输出: 3
解释: 最长公共子序列是 "ACE"

输入: text1 = "ABCBDAB", text2 = "BDCAA"
输出: 4
解释: 最长公共子序列是 "BDAB"

二、动态规划解法

2.1 状态定义

dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列长度。

2.2 状态转移方程

• 若 text1[i-1] == text2[j-1]：
  dp[i][j] = dp[i-1][j-1] + 1（当前字符匹配，LCS长度+1）
• 否则：
  dp[i][j] = max(dp[i-1][j], dp[i][j-1])（取上方或左方的最大值）

2.3 完整Java实现

public class LCS {

    // 标准二维DP解法
    public static int longestCommonSubsequence(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]);
                }
            }
        }

        return dp[m][n];
    }
}

2.4 DP表执行示例

以 text1 = "ABCBDAB", text2 = "BDCAA" 为例：

      B  D  C  A  A
   0  0  0  0  0  0
A  0  0  0  0  1  1
B  0  1  1  1  1  1
C  0  1  1  2  2  2
B  0  1  1  2  2  2
D  0  1  2  2  2  2
A  0  1  2  2  3  3
B  0  1  2  2  3  3

右下角 dp[7][5] = 4，即 LCS 长度为 4。

三、空间优化：滚动数组

观察状态转移方程，dp[i][j] 只依赖于：
– dp[i-1][j-1]（左上角）
– dp[i-1][j]（上方）
– dp[i][j-1]（左方）

因此只需保留两行即可：

public static int longestCommonSubsequenceOptimized(String text1, String text2) {
    // 确保 text2 是较短的字符串，以最小化空间
    if (text1.length() < text2.length()) {
        String temp = text1;
        text1 = text2;
        text2 = temp;
    }

    int m = text1.length();
    int n = text2.length();

    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];
}

空间复杂度从 O(mn) 降至 O(min(m, n))。

四、还原 LCS 路径

通过回溯DP表，可以还原出具体的公共子序列：

public static String getLCS(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    // 填充DP表
    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]);
            }
        }
    }

    // 从右下角回溯
    StringBuilder lcs = new StringBuilder();
    int i = m, j = n;

    while (i > 0 && j > 0) {
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            // 字符匹配，加入LCS
            lcs.append(text1.charAt(i - 1));
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--; // 来自上方
        } else {
            j--; // 来自左方
        }
    }

    return lcs.reverse().toString();
}

五、LCS 的变种与应用

5.1 最短公共超序列（SCS）

两个字符串的最短公共超序列长度 = m + n - LCS(text1, text2)

public static int shortestCommonSupersequence(String text1, String text2) {
    return text1.length() + text2.length() 
        - longestCommonSubsequence(text1, text2);
}

5.2 编辑距离与LCS的关系

对于只包含插入和删除操作（不含替换）的情况：
编辑距离 = m + n - 2 * LCS

5.3 最长重复子序列

求字符串与自身（但同一位置不能匹配两次）的LCS：

public static int longestRepeatingSubsequence(String text) {
    int n = text.length();
    int[][] dp = new int[n + 1][n + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (text.charAt(i - 1) == text.charAt(j - 1) && i != j) {
                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[n][n];
}

六、复杂度分析

七、实际应用：文本差异比较

LCS 是 Unix diff 工具和 Git 差异算法的基础。通过求两个文件内容行的LCS，可以识别出新增、删除和未改动的行：

public class DiffTool {
    public static void printDiff(String[] oldLines, String[] newLines) {
        // 将每行视为一个"字符"，求LCS
        int lcsLen = longestCommonSubsequenceLines(oldLines, newLines);

        // 不在LCS中的 oldLines 行被删除
        // 不在LCS中的 newLines 行被新增
        // ...
    }
}

八、总结

最长公共子序列问题是二维动态规划的经典代表，其状态转移直观易懂，空间优化技巧（滚动数组）是DP面试中的必考点。从LCS衍生出的最短公共超序列、编辑距离、差异比较等算法，构成了文本处理和生物信息学的基础工具链。掌握LCS的求解思路，是理解更复杂的序列比对算法（如Smith-Waterman、Needleman-Wunsch）的必要前提。