最长公共子序列

• 核心思想： 线性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开始存abfor(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];}