E05 线性DP 最长公共子序列

// 线性DP O(n^2)
#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N]; //f[i,j]表示前 i,j 个字符中的最长公共子序列的长度

int main(){
  cin>>a+1>>b+1;
  n=strlen(a+1); m=strlen(b+1);

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
      else f[i][j]=max(f[i-1][j],f[i][j-1]);
    }
  }
  cout<<f[n][m];
}

// 线性DP 滚动数组 O(n^2)
#include<bits/stdc++.h>
using namespace std;

const int N=10010;
int n,m;
char a[N],b[N];
int f[2][N]; //f[i,j]表示前 i,j 个字符中的最长公共子序列的长度

int main(){
  cin>>a+1>>b+1;
  n=strlen(a+1); m=strlen(b+1);
  
  int u=0;
  for(int i=1; i<=n; i++){
    u^=1;
    for(int j=1; j<=m; j++){
      if(a[i]==b[j]) f[u][j]=f[u^1][j-1]+1;
      else f[u][j]=max(f[u^1][j],f[u][j-1]);
    }
  }
  cout<<f[u][m];
}

// 线性DP 滚动数组 O(n^2)
#include<bits/stdc++.h>
using namespace std;

const int N=10005;
int n,m;
char a[N],b[N];
int f[2][N];

int main(){
  cin>>a+1>>b+1;
  n=strlen(a+1);m=strlen(b+1);
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      if(a[i]==b[j]) f[1][j]=f[0][j-1]+1;
      else f[1][j]=max(f[0][j],f[1][j-1]);
    }
    for(int j=1; j<=m; j++) f[0][j]=f[1][j];
  }
  cout<<f[1][m];
}

最长公共子序列

题目描述

给定两个字符串，求它们的最长公共子序列的长度。

思路分析

采用动态规划的方法。定义二维数组f[i][j]表示字符串s1的前i个字符与字符串s2的前j个字符的最长公共子序列长度。

• 当s1[i] == s2[j]时，f[i][j] = f[i-1][j-1] + 1（在之前的基础上增加1）；
• 当s1[i] != s2[j]时，f[i][j] = max(f[i-1][j], f[i][j-1])（取前i-1个s1和j个s2，或i个s1和j-1个s2的最大值）。 初始状态为f[0][j] = 0和f[i][0] = 0，即空字符串与任何字符串的最长公共子序列长度为0。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
char s1[N], s2[N];
int f[N][N];

int main() {
    scanf("%s%s", s1 + 1, s2 + 1); // 字符串从1开始存储，方便处理
    int len1 = strlen(s1 + 1), len2 = strlen(s2 + 1);
    
    memset(f, 0, sizeof(f)); // 初始化dp数组
    
    for (int i = 1; i <= len1; i++)
        for (int j = 1; j <= len2; j++)
            f[i][j] = (s1[i] == s2[j]) ? 1 + f[i-1][j-1] : max(f[i-1][j], f[i][j-1]);
    
    printf("%d\n", f[len1][len2]); 
    return 0;
}