最长公共子序列长度

_Cheems · 2023-03-02 19:42:47 · 个人记录

题意：

给你 A 串和 B 串 ，求它们的最大公共子序列长度。

设 A 串长度为 n ，B 串长度为 m ， n≤1000 ， m≤1000 （其实就是让你用 n^2 的算法）。

思路：

由于要考虑到两个字符串，因此 dp 数组是二维的。

2. A[i] ≠B[i]$ ：$dp[i][j]=max(dp[i][j-1] ,dp[i-1][j]);

最后输出 dp[n][m] 即可。

代码：

#include<bits/stdc++.h>
using namespace std;
char a[1005],b[1005];
int n,m,dp[1005][1005];
int main()
{
    scanf("%s%s",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++)
      a[i]==b[j]?dp[i][j]=dp[i-1][j-1]+1:dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    cout<<dp[n][m];
    return 0;
 }