A52016. 最长公共子序列
填空题
困难
知识点
题目描述
最长公共子序列
题目描述
给定两个字符串，寻找这两个字串之间的最长公共子序列。
输入
输入两行，分别包含一个字符串，仅含有小写字母。
输出
最长公共子序列的长度。
样例输入
abcdgh
aedfhb
样例输出
3
参考答案
#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main() {
string s1,s2;
cin>>s1>>s2;
for(int i=1; i<=s1.size(); i++) {
for(int j=1; j<=s2.size(); 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[s1.size()][s2.size()]<<endl;
return 0;
}
上一题
下一题