每日算法 — 使用java实现最长公共子序列：二维动态规划与最优子结构

问题描述

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

例如：X = “ABCBDAB”, Y = “BDCABA”
最长公共子序列为 “BCBA”，长度为4。

最优子结构

设dp[i][j]表示X的前i个字符和Y的前j个字符的LCS长度。

状态转移方程：
– 如果X[i-1] == Y[j-1]，则dp[i][j] = dp[i-1][j-1] + 1
– 如果X[i-1] != Y[j-1]，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Java完整实现

import java.util.*;

/**
 * 最长公共子序列（LCS）完整Java实现
 * 包含长度计算、路径回溯重建LCS、空间优化版本
 */
public class LongestCommonSubsequence {

    /**
     * 标准二维DP求解LCS长度
     * 时间复杂度：O(m*n)，空间复杂度：O(m*n)
     */
    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长度
        int[][] dp = 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)) {
                    // 当前字符匹配，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 reconstructLCS(String X, String Y) {
        int m = X.length();
        int n = Y.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 (X.charAt(i - 1) == Y.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 (X.charAt(i - 1) == Y.charAt(j - 1)) {
                // 字符匹配，加入LCS
                lcs.append(X.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                // 上方值更大，向上移动
                i--;
            } else {
                // 左方值更大或相等，向左移动
                j--;
            }
        }

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

    /**
     * 空间优化版本：仅使用两行
     * 时间复杂度：O(m*n)，空间复杂度：O(min(m,n))
     */
    public static int lcsLengthOptimized(String X, String Y) {
        // 确保X是较短的字符串以优化空间
        if (X.length() < Y.length()) {
            String temp = X;
            X = Y;
            Y = temp;
        }

        int m = X.length();
        int n = Y.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 (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;
        }

        return prev[n];
    }

    /**
     * 打印DP表（用于调试和理解）
     */
    public static void printDPTable(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] dp = 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;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        System.out.print("    ");
        for (int j = 0; j < n; j++) {
            System.out.print(Y.charAt(j) + " ");
        }
        System.out.println();

        for (int i = 0; i <= m; i++) {
            if (i > 0) {
                System.out.print(X.charAt(i - 1) + " ");
            } else {
                System.out.print("  ");
            }
            for (int j = 0; j <= n; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 获取所有LCS（当有多个时）
     */
    public static List<String> getAllLCS(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] dp = 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;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        List<String> result = new ArrayList<>();
        StringBuilder current = new StringBuilder();
        findAllLCS(X, Y, m, n, dp, current, result);
        return result;
    }

    private static void findAllLCS(String X, String Y, int i, int j, 
                                   int[][] dp, StringBuilder current, List<String> result) {
        if (i == 0 || j == 0) {
            result.add(current.reverse().toString());
            current.reverse(); // 恢复
            return;
        }

        if (X.charAt(i - 1) == Y.charAt(j - 1)) {
            current.append(X.charAt(i - 1));
            findAllLCS(X, Y, i - 1, j - 1, dp, current, result);
            current.deleteCharAt(current.length() - 1);
        } else {
            if (dp[i - 1][j] >= dp[i][j - 1]) {
                findAllLCS(X, Y, i - 1, j, dp, current, result);
            }
            if (dp[i][j - 1] >= dp[i - 1][j]) {
                findAllLCS(X, Y, i, j - 1, dp, current, result);
            }
        }
    }

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

        System.out.println("字符串X: " + X);
        System.out.println("字符串Y: " + Y);
        System.out.println();

        System.out.println("DP表：");
        printDPTable(X, Y);
        System.out.println();

        System.out.println("LCS长度：" + lcsLength(X, Y));
        System.out.println("LCS字符串：" + reconstructLCS(X, Y));
        System.out.println("空间优化版本LCS长度：" + lcsLengthOptimized(X, Y));

        System.out.println("
所有LCS：");
        List<String> allLCS = getAllLCS(X, Y);
        for (String s : allLCS) {
            System.out.println("  " + s);
        }
    }
}

状态转移图解

以X=”ABC”, Y=”AC”为例：

      A  C
    0  0  0
A   0  1  1
B   0  1  1
C   0  1  2

最终dp[3][2]=2，LCS为”AC”。

复杂度分析

应用场景

• 文本差异比对：Git diff、文件比较工具
• DNA序列分析：生物信息学中比较基因序列
• 拼写纠错：衡量字符串相似度
• 版本控制：追踪代码变更历史

扩展思考

1. 最长公共子串：要求子序列连续，状态转移不同
2. 最短公共超序列：dp[i][j] = dp[i-1][j-1]+1 (X[i-1]==Y[j-1]) 否则 min(dp[i-1][j], dp[i][j-1])+1
3. 编辑距离：允许插入、删除、替换操作

总结

LCS问题是理解动态规划的经典范例。其核心在于定义合适的状态表示，并通过最优子结构将大问题分解为重叠的子问题。掌握LCS有助于理解更复杂的序列比对算法如Needleman-Wunsch和Smith-Waterman。