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

答案：下面是求最长公共子序列c的代码：int lcs(char *X, char *Y, int m, int n)
{
int L[m+1][n+1];
int i, j;

/* 下面的循环填充二维数组L[][]。 */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}

/* 下面的代码用于求最长公共子序列的长度 */
return L[m][n];
}

相关问题

动态规划法求最长公共子序列c++代码，要求自己输入元素

以下是使用动态规划求解最长公共子序列的C++代码：

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

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

int main() {
    int n, m;
    cin >> n >> m;

    int a[MAXN], b[MAXN];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    memset(dp, 0, sizeof(dp));

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

    cout << dp[n][m] << endl;

    return 0;
}

这里使用了一个二维数组`dp`来保存最长公共子序列的长度，其中`dp[i][j]`表示第一个序列前i个元素与第二个序列前j个元素的最长公共子序列长度。然后通过两个for循环遍历两个序列的每个元素，如果相等则更新`dp[i][j]`，否则取`dp[i-1][j]`与`dp[i][j-1]`的较大值。最后输出`dp[n][m]`即可。

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

下面是求解最长公共子序列的 C++ 代码，其中假设两个字符串分别为 s1 和 s2：

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    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 (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];
}

这里使用了 vector<vector<int>> 来定义二维数组 dp，初始化 dp[0][0] 为0，因为两个空字符串的最长公共子序列长度为0。注意字符串的下标从0开始，所以在 dp 中的下标也要减1。最后返回 dp[m][n]，即 s1 和 s2 的最长公共子序列长度。