最长公共子序列动态规划算法

最长公共子序列（Longest Common Subsequence，LCS）动态规划算法是一种经典的动态规划算法，用于求解两个字符串的最长公共子序列。

具体算法流程如下：

1. 定义状态：

令 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符的最长公共子序列的长度。

2. 初始化状态：

当 i=0 或 j=0 时，dp[i][j]=0。

3. 状态转移：

当 s1[i-1]=s2[j-1] 时，dp[i][j]=dp[i-1][j-1]+1。

当 s1[i-1]!=s2[j-1] 时，dp[i][j]=max(dp[i-1][j],dp[i][j-1])。

4. 最终结果：

dp[m][n] 即为字符串 s1 和 s2 的最长公共子序列的长度，其中 m 和 n 分别为字符串 s1 和 s2 的长度。

需要注意的是，在求解最长公共子序列时，还需借助一个辅助数组来记录状态转移路径，以便还原出最长公共子序列。

相关问题

最长公共子序列动态规划算法c++

以下是最长公共子序列的动态规划算法的 C++ 代码实现：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 1005;

int dp[MAXN][MAXN];

int main() {
    string s1, s2;
    cin >> s1 >> s2;

    int n = s1.length(), m = s2.length();
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; 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]);
            }
        }
    }

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

    return 0;
}

其中，`dp[i][j]` 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列的长度。在状态转移时，如果两个字符相等，那么最长公共子序列的长度就是它们前面的最长公共子序列长度再加 1；否则，最长公共子序列的长度就是 s1 前 i - 1 个字符和 s2 前 j 个字符的最长公共子序列长度和 s1 前 i 个字符和 s2 前 j - 1 个字符的最长公共子序列长度的最大值。最终，`dp[n][m]` 就是 s1 和 s2 的最长公共子序列的长度。

最长公共子序列动态规划算法c语言

最长公共子序列是指在两个序列中，找到一个最长的子序列，使得它在两个序列中的相对位置都相同。下面是使用动态规划算法求解最长公共子序列的C语言代码：

#include <stdio.h>
#include <string.h>

#define MAXLEN 100    //最大序列长度

int dp[MAXLEN][MAXLEN];    //记录最长公共子序列的长度

int LCS(char *str1, char *str2, int len1, int len2)
{
    int i, j;
    //初始化第一行和第一列
    for (i = 0; i <= len1; i++)
        dp[i][0] = 0;
    for (j = 0; j <= len2; j++)
        dp[0][j] = 0;

    //动态规划求解
    for (i = 1; i <= len1; i++)
    {
        for (j = 1; j <= len2; j++)
        {
            if (str1[i-1] == str2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = (dp[i][j-1] > dp[i-1][j]) ? dp[i][j-1] : dp[i-1][j];
        }
    }
    //返回最长公共子序列的长度
    return dp[len1][len2];
}

int main()
{
    char str1[MAXLEN], str2[MAXLEN];
    int len1, len2, lcs_len;

    //读入两个字符串
    printf("请输入第一个字符串：");
    gets(str1);
    printf("请输入第二个字符串：");
    gets(str2);

    //计算最长公共子序列的长度
    len1 = strlen(str1);
    len2 = strlen(str2);
    lcs_len = LCS(str1, str2, len1, len2);

    //输出结果
    printf("最长公共子序列的长度为：%d\n", lcs_len);

    return 0;
}

其中，dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列的长度。在动态规划求解时，如果str1[i-1]等于str2[j-1]，则当前字符可以加入最长公共子序列中，此时dp[i][j]等于dp[i-1][j-1]+1；否则，当前字符不能加入最长公共子序列中，此时dp[i][j]等于dp[i][j-1]和dp[i-1][j]中的较大值。最终，dp[len1][len2]即为最长公共子序列的长度。