最长公共子序列（LCS）CSP-S

💡 核心思想

最长公共子序列（LCS）是找出两个序列的最长公共子序列（不要求连续）。经典解法是二维 DP：dp[i][j] 表示 a[1..i] 和 b[1..j] 的 LCS 长度。当 a[i] == b[j] 时，dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

🎯 直觉理解

想象你在比较两串DNA，找它们共同的基因片段。LCS 就是"不需要连续"的共同片段。比如 "ABCBDAB" 和 "BDCABA" 的 LCS 是 "BCBA"（长度为 4）。你可以画一个表格，一行一列地填，就像玩数独。

📝 算法流程

1. 初始化 dp[n+1][m+1] 全为 0
2. 遍历 i 从 1 到 n，j 从 1 到 m：
3. 如果 a[i] == b[j]，则 dp[i][j] = dp[i-1][j-1] + 1
4. 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
5. 答案为 dp[n][m]
6. 如需输出方案，从 dp[n][m] 倒推

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & a_i = b_j \\ \max(dp[i-1][j], dp[i][j-1]) & a_i \neq b_j \end{cases}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// LCS 长度
int lcs(string a, string b) {
    int n = a.size(), m = b.size();
    vector> dp(n + 1, vector(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            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]);
    return dp[n][m];
}

// LCS 具体方案（倒推）
string lcsPath(string a, string b) {
    int n = a.size(), m = b.size();
    vector> dp(n + 1, vector(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            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]);
    
    string res;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (a[i-1] == b[j-1]) { res += a[i-1]; i--; j--; }
        else if (dp[i-1][j] > dp[i][j-1]) i--;
        else j--;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string a = "ABCBDAB", b = "BDCABA";
    cout << lcs(a, b) << endl;      // 4
    cout << lcsPath(a, b) << endl;  // BCBA
    return 0;
}

⚠️ 常见坑点

📚 相关题目