题目描述
LCS
模板题吧
y总讲的超级透彻
我爱死他了
//来自算法基础课
好的我们来说题解这个正事
LCS
最长公共子!序!列!
注意区分子区间和子序列的区别
子区间:==子串,要求这个串在原序列中连贯,用字符串算法(KMP/trie树)
子序列:只要满足编号单调递增即可,没有必要是连续的,用dp
然后我们来看看LCS怎么做
首先我们来吹爆闫氏DP大法:
1.状态表示:
集合:f[i][j] = k 表示第一个序列的前i个字符
和第二个序列的前j个字符中
最长公共子序列长度为k
属性:max
2.状态设计:
集合划分:a[i]、b[j]是否在子序列当中
四种情况:
1) f[i-1][j-1]+1 选a[i]选b[i]
2) f[i][j-1] 选a[i]不选b[i]
//这个f[i-1][j]实际上并不一定以b[j]结尾,与我们上面说的这个想要的集合并不完全等价
//但是好处是这个集合包含了以b[j]为结尾的序列
//y大大说过:求max的集合划分可以重,不能漏
//这太妙了
3) f[i-1][j] 不选a[i]选b[i]
//同上
4) f[i-1][j-1] 不选a[i]不选b[i]
//这个集合是包含在3)4)两个集合中的,因此不用拿出来特别讨论
//这个集合3)4)告诉我们,一定要深入思考,不能想当然
好的代码来了来了
#include<bits/stdc++.h>
using namespace std;
const int N = 2333;
int n,lena,lenb;
char a[N], b[N];
int f[N][N];
int main() {
scanf("%d%d",&lena,&lenb);
scanf("%s%s",a+1,b+1);
for(int i=1; i<=lena; i++)
for(int j=1; j<=lenb; j++) {
f[i][j] = max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j]) f[i][j] = max(f[i][j],f[i-1][j-1]+1);
//先比前两个的max,然后如果能ab都取再加上这一种比较
}
printf("%d\n",f[lena][lenb]);
return 0;
}