Java实现最长公共子序列（LCS）详解（小白也能学会的动态规划入门教程）

为什么用动态规划？

暴力枚举所有子序列的时间复杂度太高（指数级），而动态规划算法可以高效地解决这个问题，时间复杂度仅为 O(m×n)，其中 m 和 n 分别是两个字符串的长度。

动态规划的核心思想是：把大问题拆成小问题，保存中间结果，避免重复计算。

LCS 的动态规划思路

我们定义一个二维数组 dp[i][j]，表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符的 LCS 长度。

状态转移方程如下：

• 如果 A[i-1] == B[j-1]，说明当前字符相同，则：
  dp[i][j] = dp[i-1][j-1] + 1
• 否则：
  dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

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

Java 代码实现

下面是一个完整的 Java 实现，包含计算 LCS 长度和还原 LCS 字符串的功能：

public class LongestCommonSubsequence {    // 计算 LCS 的长度    public static int lcsLength(String str1, String str2) {        int m = str1.length();        int n = str2.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 (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]);                }            }        }        return dp[m][n];    }    // 构造实际的 LCS 字符串    public static String buildLCS(String str1, String str2) {        int m = str1.length();        int n = str2.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 (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]);                }            }        }        // 从 dp 表反向构造 LCS        StringBuilder lcs = new StringBuilder();        int i = m, j = n;        while (i > 0 && j > 0) {            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {                lcs.append(str1.charAt(i - 1));                i--;                j--;            } else if (dp[i - 1][j] > dp[i][j - 1]) {                i--;            } else {                j--;            }        }        return lcs.reverse().toString();    }    // 测试方法    public static void main(String[] args) {        String A = "ABCDGH";        String B = "AEDFHR";        System.out.println("LCS 长度: " + lcsLength(A, B));        System.out.println("LCS 内容: " + buildLCS(A, B));    }}

运行结果

运行上述代码，输出为：

LCS 长度: 3LCS 内容: ADH

总结

通过本教程，你已经掌握了如何使用Java最长公共子序列算法来解决实际问题。LCS 是动态规划算法的经典案例，也是面试常考题。建议你动手敲一遍代码，加深理解。

此外，LCS 在字符串匹配、Git diff、DNA 序列比对等场景中都有重要应用。掌握它，就等于打开了一扇通往算法世界的大门！

小贴士：如果你觉得二维数组占用内存太多，还可以进一步优化为滚动数组（只保留两行），但这属于进阶内容，初学者先掌握基础版本即可。