用动态规划法最长公共子序列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的最长公共子序列的长度。