動態規劃-最長公共上升子序列-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)\)。