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

最长公共子序列（Longest Common Subsequence，LCS）是动态规划领域最具代表性的问题之一。从文本差异比对到DNA序列分析，从版本控制到拼写纠错，LCS算法无处不在。本文用Java完整实现LCS的核心求解过程，并深入讲解如何从O(m×n)空间优化到O(min(m,n))。

一、问题定义

给定两个序列 X 和 Y，找出它们最长的公共子序列的长度。子序列不要求连续，但要求相对顺序一致。

示例

• X = “ABCBDAB”
• Y = “BDCABA”

它们的LCS是 “BCBA”，长度为4。注意子序列不要求字符在原串中连续出现，只需保持相对顺序。

与最长公共子串的区别

二、动态规划状态设计

设 dp[i][j] 表示 X[0..i-1] 与 Y[0..j-1] 的LCS长度。

状态转移方程

if X[i-1] == Y[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

直观理解

• 末尾字符匹配：当前字符属于LCS的一部分，长度在去掉这两个字符的子问题基础上+1
• 末尾字符不匹配：LCS只可能来自”去掉X末尾”或”去掉Y末尾”两种情况之一，取较大者

三、基础实现：二维DP表

/**
 * 最长公共子序列（LCS）- 基础二维动态规划实现
 * 时间复杂度: O(m * n)
 * 空间复杂度: O(m * n)
 */
public class LCSBasic {

    /**
     * 计算两个字符串的最长公共子序列长度
     *
     * @param x 第一个字符串
     * @param y 第二个字符串
     * @return LCS的长度
     */
    public static int lcsLength(String x, String y) {
        int m = x.length();
        int n = y.length();

        // dp[i][j] 表示 x[0..i-1] 与 y[0..j-1] 的LCS长度
        // 多申请一行一列，方便处理边界情况（空串的LCS为0）
        int[][] dp = new int[m + 1][n + 1];

        // 填充DP表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (x.charAt(i - 1) == y.charAt(j - 1)) {
                    // 当前字符匹配，继承左上角值并+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];
    }

    /**
     * 打印DP表，便于调试理解
     */
    public static void printDPTable(String x, String y, int[][] dp) {
        System.out.print("    ");
        for (char c : y.toCharArray()) {
            System.out.printf(" %c ", c);
        }
        System.out.println();

        for (int i = 0; i <= x.length(); i++) {
            if (i > 0) {
                System.out.printf(" %c ", x.charAt(i - 1));
            } else {
                System.out.print("   ");
            }
            for (int j = 0; j <= y.length(); j++) {
                System.out.printf("%2d ", dp[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        String x = "ABCBDAB";
        String y = "BDCABA";

        System.out.println("=== 最长公共子序列（基础实现）===");
        System.out.println("字符串 X: " + x);
        System.out.println("字符串 Y: " + y);

        int length = lcsLength(x, y);
        System.out.println("\nLCS长度: " + length);
        // 预期输出: 4 (LCS为 "BCBA" 或 "BDAB")
    }
}

四、进阶：回溯求解具体LCS

仅知道长度往往不够，实际应用中通常需要得到具体的子序列内容。利用DP表进行回溯即可。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * LCS回溯实现 - 不仅返回长度，还返回具体的LCS序列
 */
public class LCSWithPath {

    /**
     * 计算LCS长度并记录方向，用于回溯
     * direction[i][j]:
     *   0 - 来自左上角（当前字符属于LCS）
     *   1 - 来自上方
     *   2 - 来自左方
     */
    public static String findLCS(String x, String y) {
        int m = x.length();
        int n = y.length();
        int[][] dp = new int[m + 1][n + 1];
        int[][] direction = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (x.charAt(i - 1) == y.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    direction[i][j] = 0; // 来自对角线
                } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                    dp[i][j] = dp[i - 1][j];
                    direction[i][j] = 1; // 来自上方
                } else {
                    dp[i][j] = dp[i][j - 1];
                    direction[i][j] = 2; // 来自左方
                }
            }
        }

        // 回溯构造LCS
        List<Character> lcsChars = new ArrayList<>();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (direction[i][j] == 0) {
                // 来自对角线，当前字符属于LCS
                lcsChars.add(x.charAt(i - 1));
                i--;
                j--;
            } else if (direction[i][j] == 1) {
                i--;
            } else {
                j--;
            }
        }

        Collections.reverse(lcsChars);
        StringBuilder sb = new StringBuilder();
        for (char c : lcsChars) {
            sb.append(c);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String x = "ABCBDAB";
        String y = "BDCABA";

        System.out.println("=== LCS回溯求解 ===");
        System.out.println("字符串 X: " + x);
        System.out.println("字符串 Y: " + y);

        String lcs = findLCS(x, y);
        System.out.println("LCS内容: \"" + lcs + "\"");
        System.out.println("LCS长度: " + lcs.length());
    }
}

五、空间优化：滚动数组

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

因此只需保留两行即可，空间复杂度从 O(m×n) 降到 O(min(m,n))。

/**
 * LCS空间优化版本 - 使用滚动数组
 * 空间复杂度: O(min(m, n))
 */
public class LCSSpaceOptimized {

    /**
     * 空间优化后的LCS长度计算
     * 始终用较短的字符串作为列方向，进一步减少空间占用
     */
    public static int lcsLengthOptimized(String x, String y) {
        // 确保 y 是较短的字符串，以最小化空间
        if (x.length() < y.length()) {
            String temp = x;
            x = y;
            y = temp;
        }

        int m = x.length();
        int n = y.length();

        // 只需要两行：previous 和 current
        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 (x.charAt(i - 1) == y.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;
            // 清空 curr 供下一轮使用（Java数组初始化即0，但交换后prev持有旧curr值，需要清空curr）
            // 实际上因为下一轮会覆盖curr的所有有效位置，所以不需要显式清空
        }

        // 最后结果在 prev 中（因为最后一次交换后，prev指向了最后一次计算的curr）
        return prev[n];
    }

    public static void main(String[] args) {
        String x = "ABCBDAB";
        String y = "BDCABA";

        System.out.println("=== LCS空间优化实现 ===");
        System.out.println("字符串 X: " + x + " (长度 " + x.length() + ")");
        System.out.println("字符串 Y: " + y + " (长度 " + y.length() + ")");

        int length = lcsLengthOptimized(x, y);
        System.out.println("LCS长度: " + length);
        System.out.println("空间复杂度: O(" + Math.min(x.length(), y.length()) + ")");
    }
}

六、最长递增子序列（LIS）与LCS的关联

一个有趣的转化：求数组的LIS，可以将其与排序后的数组求LCS。但更高效的做法是直接使用 patience sorting 结合二分查找：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 最长递增子序列（LIS）- 二分优化版本
 * 可作为LCS思想的自然延伸学习
 * 时间复杂度: O(n log n)
 */
public class LISBinarySearch {

    /**
     * 使用二分查找维护递增序列的尾部元素
     *
     * @param nums 输入数组
     * @return LIS的长度
     */
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // tails[i] 表示长度为 i+1 的递增子序列的最小尾部元素
        List<Integer> tails = new ArrayList<>();

        for (int num : nums) {
            // 在 tails 中找到第一个 >= num 的位置
            int pos = Collections.binarySearch(tails, num);
            if (pos < 0) {
                pos = -(pos + 1);
            }

            if (pos == tails.size()) {
                // num 比所有尾部元素都大，可以扩展序列
                tails.add(num);
            } else {
                // 替换，使得同样长度的序列有更小的尾部（更有潜力）
                tails.set(pos, num);
            }
        }

        return tails.size();
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};

        System.out.println("=== 最长递增子序列（二分优化）===");
        System.out.print("输入数组: ");
        for (int n : nums) {
            System.out.print(n + " ");
        }
        System.out.println();

        int length = lengthOfLIS(nums);
        System.out.println("LIS长度: " + length);
        // 预期: 4 (递增子序列 [2, 3, 7, 101] 或 [2, 5, 7, 101])
    }
}

七、复杂度分析

八、实际应用场景

• 文本差异比对：Git diff、文件比较工具的核心算法基础
• 生物信息学：DNA/RNA序列相似度分析，判断物种亲缘关系
• 拼写纠错：找出用户输入与词典中最接近的单词
• 版本控制：代码合并时识别共同片段，减少冲突
• 语音识别：将识别结果与标准文本进行序列比对
• 抄袭检测：通过LCS相似度判断文本重复程度

九、总结

最长公共子序列问题完美展示了动态规划的精髓：

1. 最优子结构：大问题最优解包含子问题的最优解
2. 重叠子问题：大量子问题被重复计算，适合用表格记忆化
3. 状态转移方程简洁清晰，是DP设计的核心产出
4. 空间优化往往依赖于对依赖关系的细致观察，滚动数组是经典技巧

从二维表格到滚动数组，从只求长度到回溯路径，LCS问题的各个变体覆盖了动态规划学习的主要知识点。掌握LCS，不仅能在面试中从容应对，更能在实际工程中处理文本比对、序列分析等常见需求。