算法基础之最长公共子序列

最长公共子序列

• 核心思想： 线性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];
      }