動态規劃-最長公共上升子序列-n^2解法

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]\)進行分類讨論。

\[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]的更新之後。
      }
  }
             

4. 總結

• 本題是最長公共子序列模型和最長上升子序列模型的結合版， 我們可以根據最長上升子序列和最長公共子序列的狀态表示方法得到啟發，建構狀态表示方法和狀态轉移方程。
• 樸素解法的時間複雜度較高，但是我們可以根據代碼進行優化，将時間複雜度由\(O(n^3)\)降到\(O(n^2)\)。