掌握Java最长公共子序列（动态规划LCS算法详解）

构建DP表

我们创建一个二维数组 dp[i][j]，其中 dp[i][j] 表示 str1 的前 i 个字符与 str2 的前 j 个字符的LCS长度。

状态转移方程如下：

• 如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
• 否则，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

Java代码实现

下面是一个完整的Java程序，用于计算两个字符串的LCS长度：

public class LCSSolution {    public static int longestCommonSubsequence(String str1, String str2) {        int m = str1.length();        int n = str2.length();                // 创建 (m+1) x (n+1) 的DP表        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]);                }            }        }                // 返回LCS长度        return dp[m][n];    }        public static void main(String[] args) {        String str1 = "ABCDGH";        String str2 = "AEDFHR";        System.out.println("LCS 长度: " + longestCommonSubsequence(str1, str2));        // 输出: LCS 长度: 3    }}

时间与空间复杂度

• 时间复杂度：O(m × n)，其中 m 和 n 分别是两个字符串的长度。
• 空间复杂度：O(m × n)，用于存储DP表。

进阶：如何输出具体的LCS字符串？

如果你不仅想知道长度，还想得到实际的LCS字符串，可以在填完DP表后，从右下角回溯构建结果：

public static String getLCSString(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]);            }        }    }        // 回溯构建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();}

总结

通过本教程，你已经掌握了如何使用Java最长公共子序列算法、理解了动态规划LCS的核心思想，并能编写完整的Java DP算法代码。无论你是准备面试，还是学习算法课程，这个最长公共子序列教程都能为你打下坚实基础。

动手试试吧！修改字符串内容，观察结果变化，加深理解。编程之路，贵在实践！