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

C++中求最长公共子序列的代码，可以使用动态规划算法来实现。具体实现步骤如下：

1. 定义两个字符串s1和s2，分别表示要求最长公共子序列的两个字符串。

2. 定义一个二维数组dp，dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子序列长度。

3. 初始化dp数组的第一行和第一列为0，即当其中一个字符串为空时，最长公共子序列长度为0。

4. 遍历s1和s2的每个字符，如果s1[i]等于s2[j]，则dp[i][j]等于dp[i-1][j-1]+1；否则dp[i][j]等于max(dp[i-1][j], dp[i][j-1])，即分别取不包含当前字符的情况下的最长公共子序列长度的最大值。

5. 最终dp[s1.size()][s2.size()]即为最长公共子序列的长度。

以下是C++代码实现：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    int dp[m+1][n+1];
    for(int i = 0; i <= m; i++) dp[i] = 0;
    for(int j = 0; j <= n; j++) dp[j] = 0;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; 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[m][n];
}

int main() {
    string s1 = "ABCD", s2 = "ACDF";
    cout << "The length of the longest common subsequence is: " << longestCommonSubsequence(s1, s2) << endl;
    return 0;
}