题目描述
给两个字符序列,这两个序列的公共子序列最长为多少?
算法1
(线性dp)
状态表示 f[i][j]
- 集合 第一个序列的前i个字符与第二个序列前j个字符公共子序列长度的最大值。
- 属性 max
状态计算
- 方程
- 当a[i] $\ne$ b[j] 时 f[i][j] = max(f[i][j-1], f[i-1][j], f[i-1][j-1])
- 当a[i] $=$ b[j] 时 f[i][j] = max(f[i][j-1], f[i-1][j], f[i-1][j-1] + 1)
时间复杂度
两层n层的循环,故时间复杂度为O(${n^2}$)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define f(i, j, k) for(int i = j; i <= k; i ++ )
const int N = 1e3 + 10;
int n, m, f[N][N];
char a[N], b[N];
inline int max(int a, int b, int c)
{
int t = a;
t = max(t, b);
t = max(t, c);
return t;
}
signed main()
{
cin >> n >> m;
cin >> a + 1 >> b + 1;
f(i, 1, n)
f(j, 1, m)
{
if(a[i] == b[j]) f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1);
else f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1]);
}
cout << f[n][m] << endl;
}