這里，為了更方便地解釋，我以洛谷上的一道典型題目為例，為大家講解處理最長公共子序列問題的幾種常見方法。這道題目中規定了兩個子序列的長度相等，如果遇到不等的情況，也只需要對長度稍作修改即可，算法思想不變。

題目描述

給出 1，2，……?，n 的兩個排列 A?和 B?，求它們的最長公共子序列。

輸入格式

第一行是一個數 n。

接下來兩行，每行為 n?個數，為自然數 1，2，……?，n 的一個排列。

輸出格式

一個數，即最長公共子序列的長度。

樣例輸入?
5?
3 2 1 4 5
1 2 3 4 5

樣例輸出?
3

提示

- 對于 50%?的數據， n <=?10^3；
- 對于 100%?的數據， n <=?10^5。

方法1：常規動態規劃

要解決這道題目，必然要使用動態規劃。既然要用到動態規劃，就要知道狀態轉移方程。我們令L[i][j] 表示序列 A 和序列 B 的最長公共子序列的長度，則狀態轉移方程如下：

若a[i]b[j]， 則 L[i][j]L[i-1][j-1] +1

若a[i]b[j]， 則 L[i][j]max (L[i][j-1]，L[i-1][j]）

以表格的形式表示整個過程如下：（這里以?3 2 1 4 5 和1 2 3 4 5為例）

i\j	0	3	2	1	4	5
0	0	0	0	0	0	0
1	0	0	0	1	1	1
2	0	0	1	1	1	1
3	0	1	1	1	1	1
4	0	1	1	1	2	2
5	0	1	1	1	2	3

填表的過程就相當于解題的過程（第0行、第0列初始值都為0），我們以第0行為參照，先從左到右填滿第1行；再以第1行為參照，從左到右填滿第2行；以此類推，當表格填完后，答案就出來了（即為L[n][n]）。

代碼如下：

# include <iostream>using namespace std;const int maxn = 1e3 + 10;
int n;
int A[maxn];
int B[maxn];
int L[maxn][maxn];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++) {//對應狀態轉移方程if (A[i] == B[j]) {L[i][j] = L[i - 1][j - 1] + 1;}else {L[i][j] = max(L[i - 1][j], L[i][j - 1]);}}}cout << L[n][n] << endl;return 0;
}

這種方法是最基本的方法。容易看出它的時間復雜度是O(n^2)；但這種方法有一個缺點，就是對空間的要求非常高，因為我們創建了一個二維數組 L，所以空間復雜度為O(n^2) ，如果 n 的值比較大，那么我們就無法創建 L數組了。因此，下面又給出了一種節省空間的辦法。

方法2：改進常規動態規劃

我們的算法思想還和原來基本一致，只不過，我們要把二維數組 L 變成一個一維數組。實現的思想如下：在填表的過程中，我們可以發現，當我們在填某一行時，我們其實只需要用到上一行的數組作為參照，表格中其他的部分并沒有用。所以，我們想到，可以只創建一個一維數組 L ，保存需要用作參照的上一行數據；用一個變量 ans 保存計算得到的需要填入表格的新值；在填寫當前一行數據的同時，更新數組 L已經遍歷過的部分（后面不再用到）為當前行的數據（相當于把當前行的數據逐步填入 L）；這樣，在填寫下一行數據時，L也已經更新為新的參照行。最后得到的 ans 就相當于原表格最右下角的位置，即為最終答案。

改進后的代碼如下：

# include <iostream>using namespace std;const int maxn = 1e5 + 10;
int n;
int A[maxn];
int B[maxn];
int L[maxn];int main()
{cin >> n;for (int i = 1; i <= n; i++) {cin >> A[i];}for (int i = 1; i <= n; i++) {cin >> B[i];}int ans = 0, t;for (int i = 1; i <= n; i++) {ans = 0;for (int j = 1; j <= n; j++) {t = ans;  //提前記錄上一個ans的值if (A[i] == B[j]) {ans = L[j - 1] + 1;}else {ans = max(ans, L[j]);}//對已經遍歷過的地方將L更新為下一行的值L[j - 1] = t;  }L[n] = ans;  }//運行到最后，ans便是原二維數組最右下角的結果cout << ans << endl;return 0;
}

方法2和方法1算法思想基本一致，時間復雜度也都是 O(n^2)，但方法2的空間復雜度只有 O(n)，顯然是方法2更勝一籌（當然，某一問題所需要的空間不大時，我們還是優先選擇方法1，因為方法1寫起來更簡便）。

但上述兩種做法，時間復雜度都是 O(n^2)。遇到某些對時間限制比較高的情況，就不適用了，所以，我們又提出了下面一種方法。

方法3：巧用另一種動態規劃

上面解決最長公共子序列問題的算法可簡稱為LCS。我們還有另一種巧妙的方法來解決這類問題，就是將LCS轉化為LIS。什么是LIS呢？LIS是解決最長遞增（或不下降）子序列的算法。LIS算法的核心思想也是動態規劃。我們先來講講轉化的過程：

能夠轉化的前提是序列A和序列B的數據范圍必須相同

我們仍以 3 2 1 4 5 和?1 2 3 4 5 為例

A: 3 2 1 4 5

B: 1 2 3 4 5

我們把A中的數據按順序變成1、2、3、4、5（變成遞增順序），即3 -> 1，2?-> 2，1?-> 3，4?-> 4，5?-> 5；然后B按照A的轉化規則進行轉化，于是變成：

A: 1 2 3 4 5
B:?3 2 1 4 5

這樣標號之后，序列的長度顯然不會改變。但是出現了一個性質：兩個序列的子序列，一定是A的子序列。而A本身就是遞增的，因此這個子序列是遞增的。換句話說，只要這個子序列在B中遞增，它就是A的子序列。于是，問題就轉化成了求B中的最長遞增子序列。

你可能覺得這樣的轉化多此一舉，但請注意，解決最長遞增子序列類問題，時間復雜度最低可以達到 O(nlogn)；也就是說，用這種方法，我們可以將求解最長公共子序列問題的時間復雜度降為O(nlogn)，這樣在處理相關問題時就可以避免時間超限的情況。

但新的問題又來了，怎么在O(nlogn)時間復雜度內求解最長遞增子序列問題？這里，我參考了別人給出的一個解釋：

我們以數列 5?2 3 1 4 為例

首先，把 5 加入答案序列中，然后遍歷到?2，發現 2<5 , 于是，我們用2替換5；然后加3，發現3>2，所以直接把3加到答案序列中，這時候就是 [2,3] ;然后遍歷到1，我們發現1<3，于是我們找到一個最小的但是比1大的數字2，然后把1替換2，為什么這么做不會影響結果呢？你可以這么想，我們當前已經求出了一個當前最優的序列，如果我們用1替換2，然后后面來一個數字替換了3，那么我們就可以得到一個更優的序列，而如果沒有數字替換3，那么這個1替換2也就是沒有貢獻的，不會影響我們結果的最優性。另外，解題時可以直接使用STL的lower_bound函數來找到一個最小的但是大于某個數字的數。

代碼如下：

# include <iostream>
# include <vector>
# include <map>using namespace std;const int maxn = 1e5 + 10;
int n;
map<int, int>m;
int B[maxn];int main()
{cin >> n;int a;for (int i = 1; i <= n; i++) {cin >> a;m[a] = i;}int b;for (int i = 1; i <= n; i++) {cin >> b;//按照A的轉化規則，轉化BB[i] = m[b];}//序列C用于保存當前的最優解vector<int>C;C.push_back(0);int len = 0; //保存最終結果for (int i = 1; i <= n; i++) {if (B[i] > C[len]) {C.push_back(B[i]);len++;}else {C[lower_bound(C.begin(), C.end(), B[i]) - C.begin()] = B[i];}}cout << len << endl;return 0;
}

用這種方法時間復雜度就降為O(nlogn)了。我上面給出的那一道題，也只有采用這種方法才不會時間超限。而前兩種只能得一半的分。

總結：

這里，我給出了解決最長公共子序列的三種方法，大家可以根據實際問題，各取所需。以上便是我的看法，很高興與大家分享。