272. 最长公共上升子序列

题目描述

给两个数组，求数组的公共最长上升子序列？

基本分析

1. 状态定义的线索？（1）需要包含两个数组；（2）需要考虑到上升的限制；
2. 状态集合？f[i][j]表示a中以前i，b中前j，且以b[j]结尾的最长公共上升子串集合；
3. 状态属性？集合中子序列长度的最大值
4. 状态计算？（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;
}

总结

1. 这里i从0开始，所以需要在i-1时候对i进行判断。i=0的时候不能从i-1转移
2. 在枚举k的时候，就默认了长度是2，对长度1的情况需要定义一个初值maxv = 1，表示倒数第二个位置是空
3. 有2个限制条件？（1）a[i] != b[j]时候，不满足假设，这一部分不转移；（2）当b[k] >= b[j]时候，也不能从这里转移

基本分析

1. 为啥能优化？当满足a[i] == b[j]时候，第三层循环存在重复计算情况，可以进行代码调优。
2. 怎么优化？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;
}

总结

1. 再体会一下b[j]改为a[i]后，优化第3层循环的思路。