动态规划实现最长公共子序列c++代码

动态规划是一种常用的算法思想，用于解决一些优化问题。最长公共子序列问题就是其中一个典型的例子。以下是实现最长公共子序列的c++代码：

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

const int N = 1010;
int dp[N][N];

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

    int n1 = s1.size(), n2 = s2.size();
    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]);
        }

    cout << dp[n1][n2] << endl;

    return 0;
}

这段代码首先读入两个字符串s1和s2，并定义dp数组表示最长公共子序列的长度。接着，双重循环遍历s1和s2中的每个字符，并根据状态转移方程进行动态规划，最后输出dp[n1][n2]即可。

相关问题

动态规划——最长公共子序列c++代码

动态规划是一种解决复杂问题的算法思想，通常用于优化具有重叠子问题和最优子结构的问题，如寻找最长公共子序列（Longest Common Subsequence, LCS）。最长公共子序列是指两个序列中的最长子序列，但顺序不一定要相同。

在C++中，可以使用二维数组来实现动态规划求解最长公共子序列。以下是一个简单的C++代码示例：

#include <iostream>
#include <vector>

std::string longestCommonSubseq(std::string str1, std::string str2) {
    int m = str1.size();
    int n = str2.size();

    // 创建一个二维数组，dp[i][j]表示str1前i个字符和str2前j个字符的最长公共子序列长度
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    // 遍历字符串，填充dp数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 从dp数组底部回溯构建最长公共子序列
    std::string result;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) {
            result = str1[i - 1] + result;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return result;
}

int main() {
    std::string str1 = "ABCDGH";
    std::string str2 = "AEDFHR";
    std::cout << "最长公共子序列: " << longestCommonSubseq(str1, str2) << std::endl;
    return 0;
}

用动态规划法最长公共子序列c++代码

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

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1005;
int dp[maxn][maxn];
int main(){
    string s1,s2;
    cin>>s1>>s2;
    int len1=s1.length(),len2=s2.length();
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;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[len1][len2]<<endl;
    return 0;
}

该代码中，我们使用一个二维数组`dp[i][j]`来表示s1的前i个字符和s2的前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]);

如果s1[i-1]和s2[j-1]相等，那么最长公共子序列就是s1的前i-1个字符和s2的前j-1个字符的最长公共子序列加上这两个字符。否则，最长公共子序列就是s1的前i-1个字符和s2的前j个字符的最长公共子序列，或者是s1的前i个字符和s2的前j-1个字符的最长公共子序列，取其中的较大值即可。最终，`dp[len1][len2]`就是s1和s2的最长公共子序列的长度。