AcWing 897. 最长公共子序列(思路超清晰)
原题链接
简单
作者:
梨小畅
,
2021-05-11 19:41:05
,
所有人可见
,
阅读 2661
思路超级清晰,一秒学会 最长公共子序列
思路
f[i][j]:A前i个字符,B前j个字符的公共子序列 的集合
属性:maxlen
集合划分:
情况1:a[i],b[j] 均存在于 最长公共子序列中 (前提a[i]==b[j])
情况2:a[i] 在,b[j] 不在 (无前提)
情况3:a[i],b[j] 均不在 (无前提)
情况4:a[i]不在,b[j]在 (无前提)
情况1:暂用f[i-1][j-1]+1表示
情况2:暂用f[i][j-1]表示
情况3:暂用f[i-1][j-1]表示
情况4:暂用f[i-1][j]表示
对于情况2暂用f[i][j-1]表示:
f[i][j-1]的含义是A前i个字符,B前j-1个字符的最长公共子序列长度 -->②
a[i]在不在该最长公共子序列中 并不一定,可能在也可能不在。
而情况2 的限制是:a[i] 一定在,b[j]一定不在 最长公共子序列中 -->①
很显然①是②的子集,即②包含了①,并不一定为①
那么我们可以继续 使用f[i][j-1]来表示情况2 吗?
答案是不可以的,但我们可以用它来表示 情况2和情况3
因为 对于 f[i][j-1],首先 a[j]一定不在 最长公共子序列中
其次,a[i]可能在 也可能不在,所以我们得到的 也就是f[i][j-1]其实是
a[i]在时 的最长公共子序列的长度 和 a[i]不在时的长度 的最大值
同理:f[i-1][j] 不能表示情况4,但可以用来表示 情况3和情况4
我们需要 求得的是 max(情况1,情况2,情况3,情况4)
而:f[i-1][j-1]+1 可以表示情况1 --> a
f[i][j-1]=max(情况2,情况3) --> b
f[i-1][j]=max(情况3,情况4) --> c
所以我们最终只需要 求 max(a,b,c) 即可
C++ 代码
#include <iostream>
using namespace std;
const int N=1010;
char a[N],b[N];
int f[N][N];
int n,m;
int main(){
cin>>n>>m;
cin>>a+1>>b+1; //下标从 1 开始
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
f[i][j]=max(f[i][j-1],f[i-1][j]);
if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
cout<<f[n][m];
return 0;
}
强
f[i-1][j-1] 的值是不是一定比f[i-1][j]和f[i][j-1]的值要小?
大佬写得太好了!!!
666
佬!绝对的佬!
牛逼,刚刚还懵逼,一看就懂了
orz
写得好,写得好
感谢大佬!!!
不赞不行啊!!
思路清晰
这思路好啊
赞
喵啊喵啊