题目描述
给定两个长度分别为N和M的字符串A和B,求既是A的子序列又是B的子序列的字符串长度最长是多少。
样例
输入
4 5
acbd
abedc
输出
3
求子序列,dp用上
集合f[i][j]属性max
为ch中前i个字符和cr中前j个字符最长的公共子序列的长度
如果当前ch=cr,那么两个都选,即为f[i-1][j-1]+1
不等的话公共子序列就只能选当前的ch(f[i][j-1]),cr(f[i-1][j])中的一个,或不选(f[i-1][j-1])
那么属性max的集合可以重,不能漏
所以,max(f[i-1[j],f[i][j-1])即可哟
//(っ'-')╮
时间复杂度
O(nm)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
char ch[1005],cr[1005];
int f[1005][1005];
int main(){
int n,m;cin>>n>>m;
cin>>ch+1>>cr+1;//i-1,j-1 ↓
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ch[i]==cr[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
cout<<f[n][m]<<"\n";
return 0;
}//码 风 奇 特,请各位见谅
//(っ’-‘)╮
类似这样的
[https://www.acwing.com/activity/content/code/content/1861646/]
我也是这样的码风,只不过中间加了点空格
没有,格式化而已,我习惯压缩并列层化的
嗯,这个还是故意弄得好看了一点的,我其他的打卡代码简直惨不忍睹呢
https://www.acwing.com/file_system/file/content/whole/index/content/1460975/
这个才是我真实的码风呢,之前的还没有习惯