最长公共子序列（LCS）算法解析与 C++ 实现

最长公共子序列（LCS）算法解析

**最长公共子序列（LCS，Longest Common Subsequence）**是动态规划中的基础算法。其解决的问题是在两个序列中找到一个序列，使得它既是第一个序列的子序列，也是第二个序列的子序列，并且该序列长度最长。

例如序列 A 为'abcdef'，序列 B 为'bcef'，那么它的最长公共子序列为'bcef'。注意最长公共子序列不要求字符连续。

暴力做法

一般的暴力做法是确定一个参照序列，遍历该序列的每一个字符，与另一个序列的每个字符比较。若相等，则继续向后匹配。时间复杂度约为 O(n^2*m)（n 为序列 A 的长度，m 为序列 B 的长度）。在实际编程中，这种复杂度往往会导致超时。

动态规划解法

为了避免重复计算，我们使用二维数组 dp[i][j] 记录状态，表示 A 序列的前 i 项与 B 序列的前 j 项所能构成的最长公共子序列长度。

状态转移方程如下：

• 当 A[i] == B[j] 时：dp[i][j] = dp[i-1][j-1] + 1
• 当 A[i] != B[j] 时：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        if(A[i] == B[j]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
        }
    }
}

此时时间复杂度为 O(n*m)，可解决大部分题目。对于更高级的场景，可利用二分优化将时间复杂度降至 O(nlogn)。

二分优化

针对特定情况（如排列问题），可将两个数组通过映射转化为一个数组，利用类似最长上升子序列的思路求解。核心口诀为：'大则添加，小则替换'。