算法1
(动态规划) $O(n^3)$
结合LCS和LIS的状态表示来想
状态表示
f[i][j]:所有由A的前i个字母,B的前j个字母构成的且以b[j]为结尾的公共上升子序列
属性
长度的max
状态划分
因为是以b[j]结尾,所以b[j]必存在,因此这里是以a[i]存不存在来划分
1) a[i]不存在,这种情况就变成了所有由A的前i - 1个字母,B的前j个字母构成的且以b[j]为结尾的公共上升子序列,即f[i - 1][j]
2) a[i]存在,这种情况存在的前提条件是a[i] == b[j]。这样的话,子序列的最后一个元素就确定了,接着我们可以参考LIS的划分思路,以倒数第二个元素来进一步划分,即有这样一些情况:不存在倒数第二个元素、倒数第二个元素为b[1]/b[2]/b[3]/......./b[j - 1]。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][N];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
int res = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) {
f[i][j] = max(f[i][j], 1);
for (int k = 1; k < j; k ++ ) {
if (b[k] < b[j]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
}
}
res = max(res, f[i][j]);
}
}
printf("%d\n", res);
return 0;
}
算法2
(动态规划 + 优化) $O(n^2)$
上述算法的复杂度可能会超时,这里对它进行优化
if (a[i] == b[j]) {
f[i][j] = max(f[i][j], 1);
for (int k = 1; k < j; k ++ ) {
if (b[k] < b[j]) { // 这里a[i] == b[j],所以可以把b[j]换成a[i]
f[i][j] = max(f[i][j], f[i - 1][k] + 1);
}
}
}
变化后
if (a[i] == b[j]) {
f[i][j] = max(f[i][j], 1);
for (int k = 1; k < j; k ++ ) {
if (b[k] < a[i]) { // 这里a[i] == b[j],所以可以把b[j]换成a[i]
f[i][j] = max(f[i][j], f[i - 1][k] + 1);
}
}
}
变化后,判断条件就和b[j]无关了,发现这段代码其实在寻找f[i - 1][1], f[i - 1][2], ......., f[i - 1][j - 1]中b[k] < a[i]的最大值,而我们的第二成循环就是对j进行枚举,而判断条件又和j无关,那么我们可以枚举j的同时,把这个也算了并记录下来
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][N];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
int res = 0;
for (int i = 1; i <= n; i ++ ) {
int maxv = 1;
for (int j = 1; j <= n; j ++ ) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
res = max(res, f[i][j]);
}
}
printf("%d\n", res);
return 0;
}