最长公共子序列

最长公共子序列(Longest Common Subsequence, LCS)问题是一个经典的动态规划问题，在字符串处理、生物信息学等领域有广泛应用。

问题定义

【定义】给定两个序列X和Y，找出X和Y的最长公共子序列。子序列是从原序列中删除零个或多个元素后得到的序列，保持剩余元素的相对顺序不变。

例如：

• 序列X = "ABCBDAB"
• 序列Y = "BDCABA"
• X和Y的最长公共子序列是"BCBA"，长度为4

动态规划解法

状态定义

设dp[i][j]表示序列X的前i个字符与序列Y的前j个字符的最长公共子序列长度。

状态转移方程

对于每一对位置(i,j)，有以下情况：

1. 如果X[i] = Y[j]，则dp[i][j] = dp[i-1][j-1] + 1 （当前字符相同，最长公共子序列可以加上这个字符）

2. 如果X[i] ≠ Y[j]，则dp[i][j] = max(dp[i-1][j], dp[i][j-1]) （当前字符不同，最长公共子序列取决于去掉X[i]或Y[j]后的最长公共子序列）

初始条件

• dp[0][j] = 0（X为空序列时，与Y的任何子序列的LCS长度为0）
• dp[i][0] = 0（Y为空序列时，与X的任何子序列的LCS长度为0）

代码实现

// 计算两个字符串的最长公共子序列长度
int longestCommonSubsequence(string X, string Y) {
    int m = X.length();
    int n = Y.length();

    // dp[i][j]表示X[0...i-1]和Y[0...j-1]的LCS长度
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            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]);
            }
        }
    }

    return dp[m][n];
}

输出最长公共子序列

除了计算LCS的长度外，有时还需要输出具体的LCS内容。可以通过回溯DP表格来实现：

// 计算并输出最长公共子序列
string getLCS(string X, string Y) {
    int m = X.length();
    int n = Y.length();

    // 计算dp数组
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            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
    string lcs;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i-1] == Y[j-1]) {
            // 当前字符是LCS的一部分
            lcs = X[i-1] + lcs;
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            // LCS来自于去掉X[i]
            i--;
        } else {
            // LCS来自于去掉Y[j]
            j--;
        }
    }

    return lcs;
}

空间优化

观察状态转移方程，dp[i][j]只依赖于dp[i-1][j-1], dp[i-1][j]和dp[i][j-1]，因此可以使用滚动数组优化空间复杂度：

// 使用滚动数组优化空间的LCS算法
int longestCommonSubsequence_optimized(string X, string Y) {
    int m = X.length();
    int n = Y.length();

    // 只使用两行dp数组
    vector<vector<int>> dp(2, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        // curr代表当前行，prev代表上一行
        int curr = i % 2;
        int prev = 1 - curr;

        for (int j = 1; j <= n; j++) {
            if (X[i-1] == Y[j-1]) {
                dp[curr][j] = dp[prev][j-1] + 1;
            } else {
                dp[curr][j] = max(dp[prev][j], dp[curr][j-1]);
            }
        }
    }

    return dp[m % 2][n];
}

更进一步，我们可以只使用一维数组（需要特别注意更新顺序）：

// 使用一维数组优化空间的LCS算法
int longestCommonSubsequence_1D(string X, string Y) {
    int m = X.length();
    int n = Y.length();

    vector<int> dp(n + 1, 0);

    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[i-1][j]
            if (X[i-1] == Y[j-1]) {
                dp[j] = prev + 1;
            } else {
                dp[j] = max(dp[j], dp[j-1]);
            }
            prev = temp;  // 为下一轮更新prev
        }
    }

    return dp[n];
}

时间和空间复杂度

• 时间复杂度：O(m*n)，其中m和n分别是两个序列的长度。
• 空间复杂度：原始算法为O(m*n)，使用滚动数组优化后为O(min(m,n))，一维数组优化为O(n)。

LCS的变种问题

最长公共子串

【问题定义】与LCS不同，最长公共子串要求子串中的字符在原字符串中是连续的。

【状态定义】dp[i][j]表示以X[i-1]和Y[j-1]结尾的最长公共子串长度。

【状态转移方程】

• 如果X[i-1] == Y[j-1]，则dp[i][j] = dp[i-1][j-1] + 1
• 否则dp[i][j] = 0

// 最长公共子串
int longestCommonSubstring(string X, string Y) {
    int m = X.length();
    int n = Y.length();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int maxLength = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i-1] == Y[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                maxLength = max(maxLength, dp[i][j]);
            } else {
                dp[i][j] = 0;  // 不连续就重置为0
            }
        }
    }

    return maxLength;
}

最长回文子序列

【问题定义】找出字符串中最长的回文子序列。

【解法】可以转化为LCS问题：计算字符串S与其反转S'的LCS即为答案。

// 最长回文子序列
int longestPalindromeSubsequence(string s) {
    string r = s;
    reverse(r.begin(), r.end());
    return longestCommonSubsequence(s, r);
}

或者直接使用DP求解：

// 直接DP求最长回文子序列
int longestPalindromeSubsequence_direct(string s) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // 单个字符是回文
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // 逐步扩展长度
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    return dp[0][n-1];
}

编辑距离

【问题定义】编辑距离是将一个字符串转换成另一个字符串所需的最少操作次数，操作包括插入、删除和替换。

【状态定义】dp[i][j]表示将字符串X的前i个字符转换成字符串Y的前j个字符所需的最少操作次数。

// 编辑距离
int editDistance(string X, string Y) {
    int m = X.length();
    int n = Y.length();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 初始化
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;  // 删除X的i个字符
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;  // 插入Y的j个字符
    }

    // 填充dp表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i-1] == Y[j-1]) {
                dp[i][j] = dp[i-1][j-1];  // 无需操作
            } else {
                dp[i][j] = 1 + min({dp[i-1][j],      // 删除
                                   dp[i][j-1],      // 插入
                                   dp[i-1][j-1]});  // 替换
            }
        }
    }

    return dp[m][n];
}

LCS的应用

1. DNA序列分析：比较DNA序列的相似性
2. 文件比较：如Git中的diff功能
3. 拼写检查：找出与错误拼写最相似的词
4. 自然语言处理：文本相似度计算
5. 图像识别：比较特征序列

LCS高级优化

最长递增子序列变形

当一个序列是1到n的排列时，可以将LCS问题转化为最长递增子序列(LIS)问题，可以优化到O(n log n)。

二分优化

基于贪心策略，可以使用二分查找来优化LCS的计算过程，适用于某些特殊情况。

稀疏DP

当两个序列很长但相同字符较少时，可以使用稀疏动态规划来优化空间和时间复杂度。

实战技巧

1. 区分LCS和最长公共子串：子序列可以不连续，子串必须连续
2. 处理多个序列：可以两两比较或使用更复杂的多维DP
3. 空间优化：根据需要选择适当的空间优化方法
4. 特殊情况：处理空序列、相同序列等边界情况
5. 输出方案：回溯时处理多个可能的LCS时，可根据需要输出字典序最小的LCS

练习题目推荐

1. POJ 1458: Common Subsequence (基础LCS题)
2. POJ 1080: Human Gene Functions (带权LCS)
3. POJ 1159: Palindrome (最长回文子序列)
4. POJ 3176: Cow Bowling (类似LCS的DP问题)
5. LeetCode 583: Delete Operation for Two Strings (LCS应用题)
6. LeetCode 1143: Longest Common Subsequence (标准LCS问题)

总结

最长公共子序列问题是动态规划的经典应用，掌握LCS的求解思路对于理解和解决其他序列比较问题至关重要。通过本章的学习，你应该能够：

1. 理解LCS问题的核心思想
2. 使用动态规划解决LCS及其变种问题
3. 应用空间优化技巧降低算法空间复杂度
4. 举一反三，解决与LCS相关的衍生问题