题目描述
给两个数组，求数组的公共最长上升子序列？
基本分析
- 状态定义的线索？（1）需要包含两个数组；（2）需要考虑到上升的限制；
- 状态集合？f[i][j]表示a中以前i，b中前j，且以b[j]结尾的最长公共上升子串集合；
- 状态属性？集合中子序列长度的最大值
- 状态计算？（1）不包含i的情况：f[i-1][j];(2)包含i的情况，继续划分；继续枚举到倒数第二个位置(f[i-1][0], f[i-1][1], ...f[i-1][j-1])。
代码1 3重循环
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
for (int i = 0; i < n; i ++) scanf("%d", &b[i]);
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < n; j ++)
{
if (i > 0)
f[i][j] = f[i-1][j];
if (a[i] == b[j])
{
int maxv = 1;
for (int k = 0; k < j; k++)
if (b[k] < b[j] && i > 0)
maxv = max(maxv, f[i-1][k] + 1);
f[i][j] = max(f[i][j], maxv);
}
}
}
int ans = 0;
for (int i = 0; i < n; i ++) ans = max(ans, f[n-1][i]);
printf("%d\n", ans);
return 0;
}
总结
- 这里i从0开始，所以需要在i-1时候对i进行判断。i=0的时候不能从i-1转移
- 在枚举k的时候，就默认了长度是2，对长度1的情况需要定义一个初值maxv = 1，表示倒数第二个位置是空
- 有2个限制条件？（1）a[i] != b[j]时候，不满足假设，这一部分不转移；（2）当b[k] >= b[j]时候，也不能从这里转移
基本分析
- 为啥能优化？当满足a[i] == b[j]时候，第三层循环存在重复计算情况，可以进行代码调优。
- 怎么优化？maxv直接放在j的外侧，只有当满足条件的时更新f[i][j]和maxv就行。
代码2 优化掉第3层
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
for (int i = 0; i < n; i ++) scanf("%d", &b[i]);
for (int i = 0; i < n; i ++)
{
int maxv = 1;
for (int j = 0; j < n; j++)
{
if (i > 0)
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] && i > 0)
maxv = max(maxv, f[i-1][j] + 1);
}
}
int ans = 0;
for (int i = 0; i < n; i ++) ans = max(ans, f[n-1][i]);
printf("%d\n", ans);
return 0;
}
总结
- 再体会一下b[j]改为a[i]后，优化第3层循环的思路。