最长公共子序列
题目 最长公共子序列
思路分析
最长公共子序列是abd长度为3
对于这种两个序列的状态表示 可以用i表示第一个序列 j表示第二个序列
f[i][j]表示 第一个序列的前i个字母 第二个序列的前j个字母构成的子序列的最大长度
这个状态转移也可以用类似于kmp的方式进行
对比第i和第j个元素 如果相同 就说明在f[i-1][j-1]的状态下 加上这个位置的相同元素 长度+1 f[i][j]=f[i-1][j-1]+1
如果不同 就有几种情况考虑了 如果序列加上a[i]能构成新的最长公共子序列 那么状态由f[i][j-1]得来 如果序列加上b[j]能构成最长公共子序列 你们状态由f[i-1][j]得来 如果两个都不行的话 状态就仍旧为f[i-1][j-1]的样子 只需要在这几种当中 选出一个max即可
状态表示：f[i][j]
集合：第一个序列的前i个字母 第二个序列的前j个字母构成的子序列
属性：Max
状态计算：
if(a[i]=b[j]) f[i][j]=f[i-1][j-1]+1
else f[i][j]=max({f[i-1][j-1],f[i][j-1],f[i-1][j]});
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int n,m;
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++){
if(a[i]==b[j])
f[i][j]=f[i-1][j-1]+1;
else
f[i][j]=max({f[i-1][j-1],f[i][j-1],f[i-1][j]});
}
}
cout<<f[n][m];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int n,m;
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-1]+(a[i]==b[j]),f[i][j-1],f[i-1][j]});
}
}
cout<<f[n][m];
return 0;
}
💬 评论