LCS最长公共子序列可视化 - 动态规划

最长公共子序列（LCS）问题是寻找两个序列共有的最长子序列。子序列不要求连续，但必须保持相对顺序。LCS是许多文本比较和生物信息学应用的基础。

动态规划思路

设 dp[i][j] 表示序列A的前i个字符与序列B的前j个字符的LCS长度。

如果 A[i-1] == B[j-1]：dp[i][j] = dp[i-1][j-1] + 1（当前字符匹配，LCS长度+1）
如果 A[i-1] != B[j-1]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（取左边或上边的较大值）

最终 dp[m][n] 就是LCS的长度。通过回溯DP表可以还原出具体的LCS序列。

时间与空间复杂度

指标	复杂度	说明
时间复杂度	O(M × N)	需要填充整个DP表
空间复杂度	O(M × N)	需要存储DP表
优化空间	O(min(M,N))	只存储两行即可（如果只需长度）

应用场景

文本比较：diff工具比较文件差异
生物信息学：DNA/蛋白质序列比对
版本控制：检测代码变更
拼写检查：计算编辑距离的基础
数据去重：识别相似内容

文本比较 DNA比对版本控制相似度计算

代码实现

def lcs(a, b):
    """计算最长公共子序列"""
    m, n = len(a), len(b)
    
    # 创建DP表
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[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字符串
    lcs_str = []
    i, j = m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            lcs_str.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(lcs_str))


# 使用示例
a = "ABCBDAB"
b = "BDCABA"
result = lcs(a, b)
print(f"LCS: {result}, 长度: {len(result)}")
# 输出: LCS: BCBA, 长度: 4

public class LCS {
    
    /**
     * 计算最长公共子序列
     */
    public static String lcs(String a, String b) {
        int m = a.length();
        int n = b.length();
        
        // 创建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 (a.charAt(i - 1) == b.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 lcsStr = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                lcsStr.insert(0, a.charAt(i - 1));
                i--; j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        
        return lcsStr.toString();
    }
    
    public static void main(String[] args) {
        String a = "ABCBDAB";
        String b = "BDCABA";
        String result = lcs(a, b);
        System.out.println("LCS: " + result + 
            ", 长度: " + result.length());
        // 输出: LCS: BCBA, 长度: 4
    }
}