最长公共子序列问题c++代码

最长公共子序列（Longest Common Subsequence, LCS）问题是一个经典的计算机科学问题，涉及到找到两个序列中最长的共同部分，但是可以不需要按照顺序匹配。这里有一个简单的C++代码，使用动态规划来解决这个问题：

#include <iostream>
#include <vector>
using namespace std;

// 定义函数求LCS长度
int lcs(string X, string Y, int m, int n) {
    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];
}

int main() {
    string X = "AGGTAB";
    string Y = "GXTXAYB";
    int m = X.length();
    int n = Y.length();

    cout << "Length of LCS is: " << lcs(X, Y, m, n) << endl;

    return 0;
}

这段代码创建了一个二维动态规划矩阵dp，其中`dp[i][j]`表示字符串X前i个字符和Y前j个字符的最长公共子序列长度。如果`X[i-1]`和`Y[j-1]`相同，那么它们可以作为最长公共子序列的一部分，所以将上一行和上一列的值加1；否则取两者的较大值。