C++中最长公共子序列的代码

下面是求解C++中最长公共子序列（Longest Common Subsequence，简称LCS）的代码示例：

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

const int MAXN = 1005;
int dp[MAXN][MAXN];

int lcs(string s1, string s2) {
    int n1 = s1.length(), n2 = s2.length();
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (s1[i-1] == s2[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[n1][n2];
}

int main() {
    string s1 = "abcde";
    string s2 = "ace";
    cout << lcs(s1, s2) << endl;
    return 0;
}

在上面的代码中，我们使用DP（动态规划）求解最长公共子序列。首先，我们定义一个二维数组`dp`，其中`dp[i][j]`表示`s1`的前`i`个字符和`s2`的前`j`个字符的最长公共子序列的长度。然后，我们对`dp`数组进行填表，具体的状态转移方程如下：

if (s1[i-1] == s2[j-1]) {
    dp[i][j] = dp[i-1][j-1] + 1;
} else {
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}

如果`s1[i-1]`等于`s2[j-1]`，说明`s1`和`s2`在第`i`个和第`j`个位置上的字符相同，那么最长公共子序列的长度就等于`s1`的前`i-1`个字符和`s2`的前`j-1`个字符的最长公共子序列的长度再加上1，即`dp[i-1][j-1] + 1`。否则，说明`s1`和`s2`在第`i`个和第`j`个位置上的字符不同，那么最长公共子序列的长度就等于`s1`的前`i-1`个字符和`s2`的前`j`个字符的最长公共子序列的长度，或者是`s1`的前`i`个字符和`s2`的前`j-1`个字符的最长公共子序列的长度的最大值，即`max(dp[i-1][j], dp[i][j-1])`。最后，返回`dp[n1][n2]`即可。