动态规划-最长公共上升子序列-n^2解法

hewendong 2021-03-11 原文

1. 题目描述

给定两个数列\(A, B\)，如果他们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列。求\(A\)和\(B\)的最长公共上升子序列。

输入格式

第一行包含一个整数\(N\)，表示\(A\)和\(B\)的长度。

第二行包含\(N\)个整数，表示数列\(A\)。

第三行包含\(N\)个整数，表示数列\(B\)。

输出格式

输出一个整数，表示最长公共上升子序列的长度。

数据范围

\(1 ≤ N≤ 3000\)，序列中的数字均不超过\(2^{31} – 1\).

输入样例

4
2 2 1 3
2 1 2 3

输出样例

2. 朴素解法\(O(n^3)\)

朴素解法将最长公共子序列和最长上升子序列模型相结合。

用\(f[i][j]\)表示第一个序列的前\(i\)个数，和第二个序列的前\(j\)个数，且最后一个数为\(b[j]\)的最长公共上升子序列的长度。

则可以根据\(a[i]\)是否等于\(b[j]\)进行分类讨论。

\[f[i][j]=\left\{
\begin{array}{rcl}
f[i – 1][j] & & {a[i] != a[j]}\\
max_{k < j且b[k] < b[j]}(f[i][j], f[i- 1][k]) & & {a[i] == b[j] }\\

\end{array} \right.
\]

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int a[N], b[N];
int n;
int f[N][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];
    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);
            }
        }
    }
    int res = 0;
    for(int i = 1;i <= n; i ++) res = max(res, f[n][i]);
    cout << res << endl;
    return 0;
}

3. 代码优化\(O(n^2)\)

上述朴素做法的时间复杂度为\(O(n^3)\)。那么我们如何优化呢?

观察代码的最内层循环部分

 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);
 }

由于执行最内层循环的时候a[i] == b[j]。所以最内层条件可以变为b[k] < a[i]。

再来考虑整个循环

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] < a[i]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
        }
    }
}

我们实际上就是在求：当第一个循环走到i，第二个循环走到j 且满足” a[i] > b[k]且k < j “时f[i - 1][j]的最大值。

也就是说当我们访问到第j层循环的时候，需要前j-1层的数据。因此，可以在j的循环中迭代求解。

代码如下

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);  // maxv的更新一定要在f[i][j]的更新之后。
    }
}