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

• 2021 年 3 月 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

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

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

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

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

#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]的更新之后。
      }
  }
  

4. 总结

• 本题是最长公共子序列模型和最长上升子序列模型的结合版， 我们可以根据最长上升子序列和最长公共子序列的状态表示方法得到启发，构建状态表示方法和状态转移方程。
• 朴素解法的时间复杂度较高，但是我们可以根据代码进行优化，将时间复杂度由\(O(n^3)\)降到\(O(n^2)\)。