每日算法 — 使用java实现LCS：动态规划与滚动数组优化求最长公共子序列

引言

最长公共子序列（Longest Common Subsequence，LCS）是经典的字符串/序列比对问题，广泛应用于生物信息学（DNA序列比对）、版本控制（diff工具）、拼写纠错等领域。给定两个字符串，求它们最长的公共子序列的长度。本文用Java实现标准动态规划解法，并深入讲解滚动数组空间优化技巧，将空间复杂度从 O(m×n) 降至 O(min(m,n))。

问题定义

输入：两个字符串 text1 和 text2。
输出：它们的最长公共子序列的长度。

示例：
– text1 = “abcde”, text2 = “ace”
– 输出：3
– 解释：LCS 为 “ace”

动态规划解法（O(m×n) 空间）

核心思想

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

状态转移：
– 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
– 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Java实现

public class LCS_StandardDP {

    /**
     * 标准二维DP解法，时间 O(m*n)，空间 O(m*n)
     */
    public static int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null) {
            return 0;
        }

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

    /**
     * 同时返回具体的LCS字符串
     */
    public static String getLCS_String(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]);
                }
            }
        }

        // 从右下角回溯构造LCS
        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();
    }

    public static void main(String[] args) {
        String s1 = "abcde";
        String s2 = "ace";
        System.out.println("text1: " + s1 + ", text2: " + s2);
        System.out.println("LCS长度: " + longestCommonSubsequence(s1, s2));
        System.out.println("LCS字符串: " + getLCS_String(s1, s2));

        String s3 = "abc";
        String s4 = "abc";
        System.out.println("\ntext1: " + s3 + ", text2: " + s4);
        System.out.println("LCS长度: " + longestCommonSubsequence(s3, s4));
    }
}

滚动数组优化（O(min(m,n)) 空间）

核心思想

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

因此我们只需要保留上一行和当前行，甚至只用一维数组就能完成计算。

优化技巧：使用一维数组 dp[j]，从右向左更新，这样 dp[j-1] 是已经更新过的当前行值，dp[j] 是上一行的值。

Java实现

public class LCS_RollingArray {

    /**
     * 一维滚动数组优化，空间复杂度 O(min(m,n))
     * 始终让较短的字符串作为列维度，进一步减少空间
     */
    public static int longestCommonSubsequence_optimized(String text1, String text2) {
        if (text1 == null || text2 == null) {
            return 0;
        }

        // 确保 text1 是较长的字符串，text2 是较短的
        // 这样 dp 数组的大小为 text2.length()+1
        if (text1.length() < text2.length()) {
            String temp = text1;
            text1 = text2;
            text2 = temp;
        }

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

        // 只使用一维数组，长度为较短字符串+1
        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[j]（即上一行的 dp[i-1][j]），下一轮它就是左上角

                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[j] = prev + 1; // 使用左上角的值
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]); // max(上方, 左方)
                }

                prev = temp; // 更新左上角为当前保存的值
            }
        }

        return dp[n];
    }

    /**
     * 使用两个一维数组的版本（更易理解）
     */
    public static int longestCommonSubsequence_twoRows(String text1, String text2) {
        if (text1 == null || text2 == null) {
            return 0;
        }

        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]);
                }
            }
            // 交换 prev 和 curr
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }

        return prev[n];
    }

    public static void main(String[] args) {
        String s1 = "pmjghexybyrgzczy";
        String s2 = "hafcdqbgncrcbihkd";

        System.out.println("text1: " + s1);
        System.out.println("text2: " + s2);
        System.out.println("滚动数组LCS长度: " + longestCommonSubsequence_optimized(s1, s2));
        System.out.println("双行数组LCS长度: " + longestCommonSubsequence_twoRows(s1, s2));

        // 大规模测试
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for (int i = 0; i < 5000; i++) {
            sb1.append((char) ('a' + (i % 26)));
            sb2.append((char) ('a' + ((i + 5) % 26)));
        }
        System.out.println("\n大规模测试(5000字符): " + 
            longestCommonSubsequence_optimized(sb1.toString(), sb2.toString()));
    }
}

复杂度分析

扩展应用

1. 最长重复子数组：将LCS改为连续子串问题，状态转移稍有不同
2. 编辑距离（Levenshtein Distance）：在LCS基础上增加替换/插入/删除的代价
3. DNA序列比对：生物信息学中BLAST算法的基础
4. diff算法：Git diff、Myers diff 都基于最长公共子序列思想
5. 最短公共超序列（SCS）：m + n – LCS(text1, text2)

总结

最长公共子序列问题是二维动态规划的经典代表。标准解法直观易懂，而滚动数组优化则展示了动态规划中空间优化的核心思想：分析状态依赖关系，只保留必要的状态。这种”降维”技巧在背包问题、区间DP等场景中同样适用。掌握LCS的求解与优化，是迈向高级动态规划的重要一步。