动态规划-最长公共子序列
关键点
设两个字符串分别为s1,s2;长度分别为m,n
用数组dp[i][j]
表示 以s1[i]作为结尾的字符串 和 以s2[j]作为结尾的字符串 的最长公共子序列的长度,因此最后要求的结果也就是dp[m][n]
的值
注意
1.使用scanf来读取char s1[N],不要用cin读取,可能会超时
2.两个字符串需要从下标1开始,这样便于处理dp数组的边界问题
知识点积累–关于scanf读取字符串
#include<cstdio>
#include<cstring>
char s1[N];
scanf("%s",s1);
scanf("%s",s1+1);//这个方式就会自动从下标1开始放
int len=strlen(s1+1);//字符串长度,如果是放入下标1,也要从s1+1开始读取字符串长度
完整代码
#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>//strlen()
using namespace std;
const int N = 1010;
char s1[N],s2[N];
int dp[N][N];
int main(){
while(scanf("%s%s",s1+1,s2+1)!=EOF){
int m=strlen(s1+1);
int n=strlen(s2+1);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s1[i]==s2[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[m][n]<<endl;
}
return 0;
}