最长公共子序列
-
核心思想: 线性dp
-
集合定义 : f[i][j]存 a[1 ~ i] 和 b[1 ~ j] 的最长公共子序列长度
-
状态计算: 分为取/不取a[i]/b[j] 共四种情况
- 其中 中间两种会包含两个都不取的情况(去掉) 但是因为取最大值 有重复也没事
- 用f[i-1][j] 和 f[i][j-1]表示取一个的情况即可 如果是求和 则必须去掉重复部分
-
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1010; int n,m; char a[N],b[N]; int f[N][N]; int main() { cin>>n>>m>>a+1>>b+1; //从1开始存ab for(int i=1;i<=n;i++) { for(int j=1;j<=m;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); //a[i]=b[j] 才有最后一种情况 } } cout<<f[n][m]; }
-