最长公共上升子序列

状态表示：f[i][j] 所有由第一个序列的前i个字母，第二个序列的前j个字母构成的且以b[j]结尾的公共上升子序列 的最大值。

$ 时间复杂度O(N^3)，空间复杂度O(N^2) $

参考文献

算法提高课

AC代码

#include <iostream>
using namespace std;

const int N = 3010;

int f[N][N];
int a[N], b[N];
int n;

int main(){
    //读入
    cin >> n;
    for (int i = 1 ; i <= n ; i ++) cin >> a[i];
    for (int i = 1 ; i <= n ; i ++) cin >> b[i];
    //DP
    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 - 1][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);
                }
            }
        }
    }
    //计算答案
    int res = 0 ;
    for (int i = 1 ; i <= n ; i ++) res = max(res, f[n][i]);
    cout << res ;
    return 0;
}

时间优化

我们发现枚举上升序列中，对于每一个j来说，我们都需要枚举前面的j，跟i无关，我们只需要用一个变量边枚举边将最长的序列长度存着就行。

这样能优化掉一维枚举k，时间复杂度O(N^2^)

#include <iostream>
using namespace std;

const int N = 3010;

int f[N][N];
int a[N], b[N];
int n;

int main(){
    //读入
    cin >> n;
    for (int i = 1 ; i <= n ; i ++) cin >> a[i];
    for (int i = 1 ; i <= n ; i ++) cin >> b[i];
    //DP
    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 (b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }
    //计算答案
    int res = 0 ;
    for (int i = 1 ; i <= n ; i ++) res = max(res, f[n][i]);
    cout << res ;
    return 0;
}