题目描述
给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串,表示字符串 A。
第三行包含一个长度为 M 的字符串,表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N,M≤1000
样例
输入样例:
4 5
acbd
abedc
输出样例:
3
算法1
(线性dp)
闫氏dp分析一下
集合分割:
首先,将a[i]和b[j]单独拎出来讨论,a[i]和b[j]都有“有”和“无”两种情况,一共是四种情况,假设有表示成1,无是0
那么就是
我们可以很轻易的得到00,和11的两种情况分别是f[i-1][j-1]和f[i-1][j-1]+1
所以
这时候,我们可以自然地想到中间的两个部分可以分别表示为f[i-1][j]和f[i][j-1]
注意:这里的两个概念有所不同,f[i-1][j]表示的是a[i-1]之前和b[j]之前的字符串最大值,而我们要表示的是包含了b[j]的公共子序列,两者概念不同,具体大小是f[i-1][j]包含我们需要的集合
但是,
正是因为这种包含关系,我们可以使用f[i-1][j]替代掉我们要求的东西,因为我们要求的是一个集合的最大值,所以在这里并不影响
同理可得,f[i-1][j]和f[i][j-1]都包含了f[i-1][j-1],所以,我们可以直接把第一部分给他忽略掉,仅仅进行三个部分比较即可
时间复杂度
参考文献
C++ 代码
#include<iostream>
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;//输入,两重循环
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]<<endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla