超正宗题解
原题链接：7954.最长公共子序列
2025-11-01 14:19:56
发布于：浙江
0阅读
0回复
0点赞
#include <iostream>
using namespace std;
/*
最大公共子序列（LCS）：dp[i][j]表示选择第一个字符串的前i位和第二个字符串的前j位组成的
最大公共子序列长度
状态转移方程式： s1[i]==s2[j] dp[i][j]=dp[i-1][j-1]+1 如果相等，再上一个选择的情况下+1
s1[i]!=s2[j] dp[i][j]=max(dp[i-1][j],dp[i][j-1])
是选择s1的第i位还是选择s2的第j位构成的最大LCS
初始化：无
返回结果：dp[s1.size()][s2.size()]
*/
string s1,s2;
int dp[1005][1005];
int main(){
cin>>s1>>s2;
int len1=s1.size(),len2=s2.size();
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];
return 0;
}
这里空空如也
有帮助，赞一个