最长公共子序列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 的最长公共子序列长度。

相关问题

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

### 回答1：

答案：下面是求最长公共子序列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];
}

### 回答2：
最长公共子序列（Longest Common Subsequence）是指两个序列中都能找到的最长的子序列。以下是一个用动态规划解决最长公共子序列问题的代码。

假设有两个序列A和B，长度分别为m和n。我们用一个二维数组dp来保存最长公共子序列的长度。dp[i][j]表示序列A的前i个元素和序列B的前j个元素的最长公共子序列的长度。

具体步骤如下：
1. 首先，初始化dp数组的第一行和第一列为0，即dp[0][j] = dp[i][0] = 0。
2. 然后，遍历整个二维数组dp，根据状态转移方程来计算dp[i][j]的值。如果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])。
3. 最后，dp[m][n]即为序列A和序列B的最长公共子序列的长度。

下面是伪代码实现：

function longestCommonSubsequence(A, B):
m = length(A)
n = length(B)
dp = array(m+1, n+1)

for i from 0 to m:
dp[i][0] = 0

for j from 0 to n:
dp[0][j] = 0

for i from 1 to m:
for j from 1 to n:
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])

return dp[m][n]

注意，上述伪代码还需要对序列A和B进行索引的调整，因为数组的索引通常是从1开始的，而不是从0开始的。

最终的结果就是两个序列的最长公共子序列的长度。

### 回答3：
最长公共子序列（Longest Common Subsequence）是一种常见的动态规划问题，可以采用动态规划的方法解决。下面给出一个用Python语言实现的求解最长公共子序列的代码：

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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])
    
    lcs_length = dp[m][n]
    lcs = [''] * lcs_length
    
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs[lcs_length - 1] = s1[i - 1]
            i -= 1
            j -= 1
            lcs_length -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(lcs)


s1 = "ABCD"
s2 = "ACDF"
lcs = longest_common_subsequence(s1, s2)
print(lcs)

以上代码中，首先定义一个二维数组dp来存储最长公共子序列的长度。然后利用两个嵌套的循环遍历字符串s1和s2，当两个字符相等时，可以从当前字符向前移动，并将dp[i][j]更新为dp[i-1][j-1]+1，否则，分别向上或向左移动，取dp[i-1][j]和dp[i][j-1]中的较大值。最后，根据dp数组的结果，通过回溯可以求得最长公共子序列。输出结果为"ACD"。

最长公共子序列C++代码实现

以下是最长公共子序列的 C++ 代码实现：

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

int lcs(string X, string Y, int m, int n)
{
    int L[m+1][n+1];
    for (int i=0; i<=m; i++)
    {
        for (int 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];
}

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;
}

输出结果为：

Length of LCS is: 4

其中，L[m+1][n+1]表示长度为 m 和 n 的两个字符串的最长公共子序列的长度，X[i-1]表示第一个字符串 X 的第 i 个字符，Y[j-1]表示第二个字符串 Y 的第 j 个字符。