最長公共子序列問題描述

注意：最長公共子序列不一定是連續序列。
例如："ASAFAGAHAJAK“與”AAAAAAA"的最長公共子序列為：AAAAAA

公共子序列的定義

證明最優子結構性質

分析其遞歸關系式

分別將第一個序列的元素個數設置為0到m，在每一個第一個序列的元素個數0到m的情況下，用內循環讓第二個序列的元素從0到n遍歷。

也就是說，先從0開始，求解很小的子問題，然后將這些子問題的解存儲起來，當求解更大的問題時，會用到這些子問題的結果。這時，直接訪問之前計算過的結果，避免了重復運算，這就是動態規劃的巧妙之處，也正是需要證明其最優子結構性質的原因。

計算最優值

運行效果

c數組表示當前狀態下，最長公共子序列的長度。
s數組表示當前狀態下，最長公共子序列的長度是由哪種情況（1/2/3）計算出來的。

調試中的一個過程截取：

比如說，求解ABCDEFGHI和BDFI的最長公共子序列。

第一步(填0)：
當i=0,j=0,1,2,3,...時，因為X={}，所以最長子序列都是0

第二步(填0)：i=1,2,3,...,j=0時，因為Y={}，所以最長子序列是0
(用這樣的原理，把第一行和第一列都設置為0)

第三步(進入正常循環)：
當i=1,j=1時，也就是說當X的長度為1，Y的長度為1的條件下，X={A}，Y={B}，屬于情況三（X Y的最后一個元素不相等）
此時，比較X={}，Y={B} 與 X={A}，Y={}這兩種情況下的公共子序列的值，將二者最大值（本例中為0）記錄在數c數組中的c[i][j]位置。
同時，這種情況屬于第三種，記為s[i][j]=3

…
根據第三步類推
…

某一個計算瞬間的詳細分析如下

下圖為調試過程中，截取的i=2,j=4時候的情況。當前被填寫的數組元素：c[2][4]

此時，X={A,B}，Y={B,D,F,I}
比較X與Y的最后一個元素，分別為B，I。發現其屬于情況三（X Y的最后一個元素不相等）

于是，比較X去掉最后一個元素的最長公共子序列 和 Y去掉最后一個元素的最長公共子序列，比較過程如下：
X去掉最后一個元素后，X={A}，Y={B,D,F,I}，查c數組得：其最長公共子序列為 c[i-1][j]=0
Y去掉最后一個元素后，X={A,B}，Y={B,D,F}，查c數組得：其最長公共子序列為 c[i][j-1]=1
比較結果為：取最大（后者）。 c[i][j] = c[i][j - 1] = 1，即另 c[2][4] = c[2][3] = 1

同時，因為是情況三，所以另 s[2][4] = 3。

從下圖可以看到，c[2][4] = 1已經被填入生效。剛才的分析與實際運行結果相匹配。

…其余中間過程省略

完整填寫c數組和s數組之后，最終執行結果↓

補充：填表的順序圖示

輸出：BDFI

輸出的過程

輸出序列字母的過程是一個遞歸的過程。

見下圖，根據s數組判斷下一個箭頭的指向。可以把s數組的3種情況分別對應到三個指向的箭頭，放在數組表格中。然后從右下角的元素開始，一步一步沿著箭頭向前走。

或者單步跟蹤一下代碼比較容易理解。

詳細輸出過程圖示：

代碼

注意：需要在宏定義中手動輸入序列X，Y的長度，在main函數中輸入序列X，Y的具體序列

#include<iostream> #include<cstring> #define XLEN 12 #define YLEN 7 using namespace std;int c[XLEN + 1][YLEN + 1];//Xi Yj的最長公共子序列的長度 多出1行用來存放長度為0的情況 int s[XLEN + 1][YLEN + 1];//c[i][j]的值是由哪一個子問題的解得到的void lcsLength(string x, string y) {for (int i = 0; i <= XLEN; i++) c[i][0] = 0;for (int i = 0; i <= YLEN; i++) c[0][i] = 0;for (int i = 1; i <= XLEN; i++) //xi的長度{for (int j = 1; j <= YLEN; j++) //yj的長度{if (x[i - 1] == y[j - 1]) //x y序列 最后一個元素相等{c[i][j] = c[i - 1][j - 1] + 1;s[i][j] = 1;}else //x y序列 最后一個元素不相等{if (c[i - 1][j] >= c[i][j - 1]) //x去掉現有序列最后一個元素更大{c[i][j] = c[i - 1][j];s[i][j] = 2;}else //y去掉現有序列最后一個元素更大{c[i][j] = c[i][j - 1];s[i][j] = 3;}}}} } void lcs(int i, int j, string x) {if (i == 0 || j == 0)return;if (s[i][j] == 1) //x[i] == y[j]{lcs(i - 1, j - 1, x);cout << x[i - 1];}else if (s[i][j] == 2)//c[i - 1][j] >= c[i][j - 1]{lcs(i - 1, j, x);}else lcs(i, j - 1, x);//c[i - 1][j] < c[i][j - 1] }int main() {string x = "ASAFAGAHAJAK";string y = "ASAAAAA";lcsLength(x, y);lcs(XLEN, YLEN, x);cout << endl;system("pause"); }

總結

以上是生活随笔為你收集整理的【算法设计与分析】最长公共子序列问题 动态规划算法 超详细的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。