最近朋友讓幫做個關于動態規劃的最長公共子序列的問題,翻看以前的筆記并完成該題后,順便寫這樣一篇文章,希望對大家有所幫助,同時也幫助自己回顧該知識點.

一.最長公共子序列的定義

子序列:若給定序列X={x1,x2,…,xm},則另一序列Z={z1,z2,…,zk},是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有:zj=xij.
公共子序列:給定2個序列X和Y,當另一序列Z既是X的子序列又是Y的子序列時,稱Z是序列X和Y的公共子序列.
最長公共子序列:給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最長公共子序列.
如：序列ABCDEF和ADFGH的最長公共子序列為ADF

注意:最長公共子串(Longest Common Substirng)和最長公共子序列(Longest Common Subsequence,簡稱LCS)的區別為是最長公共子串的串是一個連續的部分,而最長公共子序列則是從不改變序列的順序,而從序列中去掉任意的元素而獲得新的序列;通俗的說就是子串中字符的位置必須是連續的而子序列則可以不必連續.

二.最優子結構性質

設序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk} ,則
??? (1)若xm=yn,則zk=xm=yn,且z1,z2,…, zk-1是否為x1,x2,…,xm-1和y1,y2,…,yn-1的最長公共子序列.
??? (2)若xm≠yn且zk≠xm,則Z是x1,x2,…,xm-1和Y的最長公共子序列.
??? (3)若xm≠yn且zk≠yn,則Z是X和y1,y2,…,yn-1的最長公共子序列.

由此可見,2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列.因此,最長公共子序列問題具有最優子結構性質.當問題具有最優子結構性質和子問題重疊性質時就可以用動態規劃算法解決該問題.

三.動態規劃方法分析

由最長公共子序列問題的最優子結構性質建立子問題最優值的遞歸關系.用c[i][j]記錄序列和的最長公共子序列的長度.其中,Xi={x1,x2,…,xi},Yj={y1,y2,…,yj}.當i=0或j=0時,空序列是Xi和Yj的最長公共子序列.故此時C[i][j]=0.其它情況下,由最優子結構性質可建立遞歸關系如下:

其對應的核心代碼如下:

//參數:x字符串長度為m y字符串長度為n void LCSLength(char x[], char y[],int m，int n) { /* 計算最長公共子序列的長度 */int L[m][n],i，j;for (i = 0; i <= m; i++) L[i][0] = 0;for (i = 0; i <= n; i++) L[0][i] = 0;for (i = 1; i <= m; i++){for (j = 1; j <= n; j++) {if (x[i]==y[j]) L[i][j]=L[i-1][j-1]+1;else if (L[i-1][j]>= L[i][j-1])L[i][j]= L[i-1][j]; else L[i][j]= L[i][j-1];}} return L[m][n]; }

例如:輸入字符串“bdcaba”和"abcbdab",求它們的最長公共子序列長度.在《算法設計與分析》課程中我們老師講述的方法通常是使用動態規劃填充表格方法解決.初始時,X字符串的長度為m,Y字符串的長度為n.c[m,n]二位數組如上面遞歸關系遞歸,最后的c[m,n]為最大數字即最長公共子序列的長度.

其中從表中找出最長公共子序列的方法

?

??? (1) 從(m,n)到(0,0)

?

??? (2) 若當前格與左邊一格相同,則畫"?一";若當前格與上邊一格相同,則畫"|";上兩者都不符合,從當前格到左上格化斜線箭頭"\"; ??? (3) 從當前格向箭頭方向前進一格,對此格進行(2) ??? (4) 從(m,n)到(0,0)的不同路徑中,斜線箭頭"\"相對應的格的元素構成最長公共子序列.如圖bcbd、bcdb、badb.

四.問題的提出與解決

1.問題

題目:求兩個字符串的最長公共子序列的長度.
輸入:第一行字符串S1,第二行字符串 S2 (1<=字符串長度<=1000).輸出:數字M,為最長公共子序列長度.測試用例如下:
輸入
BDCABA
ABCBDAB
輸出
4
輸入
ABKLMNABCDI
ABCDEFGHIJKLMNOPQRSTUVWXYZ
輸出
6

?

2.代碼

?

#include <stdio.h> #include <stdlib.h> #include <string.h> int *pln1 , *pln2; char a[10010] , b[10010]; int main() {int i , j , lena , lenb ;gets(a);gets(b);lena = strlen(a);lenb = strlen(b);pln1 = (int*)calloc( lenb + 1 , sizeof(int) );memset( pln1 , 0 , sizeof(pln1) );pln2 = (int*)calloc( lenb + 1 , sizeof(int) );memset( pln2 , 0 , sizeof(pln2) );for( i = 1 ; i <= lena ; i++ ){for( j = 1 ; j <= lenb ; j++ ){if( a[i-1] == b[j-1] ){pln2[j] = pln1[j-1] + 1;}elseif( pln1[j] >= pln2[j-1] ){pln2[j] = pln1[j];}else{pln2[j] = pln2[j-1];}}free(pln1);pln1 = pln2;pln2 = (int*)calloc( lenb + 1 , sizeof(int) );memset( pln2 , 0 , sizeof(pln2) );}printf( "%d\n" , pln1[lenb] );return 0; }

五.問題的升華與解決

1.升華問題

輸入:輸入文件中的第1行是一個正整數T(0<T<=10),表示有T組測試數據.接下來是每組測試數據的描述,每組測試數據有3行.測試數據的第1行有2個正整數m、n,中間用一個空格隔開(0<m，n<50);第2、3行是長度分別為m、n的2個序列X和Y,每個序列的元素間用一個空格隔開.序列中每個元素由字母、數字等構成.輸入直到文件結束

輸出:對輸入中的每組測試數據,先輸出Case #表示第幾組數據,在輸出最長公共子序列,輸出所有的最長公共子序列,并輸出動態規劃表格c表和b表.(測試用例見結果圖)

2.代碼

這里涉及到一個新的問題：就是使用上面所敘述的填充表格來實現動態規劃,其中c[m,n]記錄的是當前序列的最長子序列長度;還需要引用一個吧b[m,n]表來尋找所有最長公共子序列,并把結果存入到result[]數組中.其中最重要的代碼就是兩個實現的函數,如下:

?

第一個LSCLength函數是求最長公共子序列長度的函數,并在該函數中填充c[m][n]和b[m][n].

?

//函數：計算最優值 //參數：m字符串X長 n字符串Y長 X字符串 Y字符串 b標志數組尋找所有字符串用 int LSCLength( int m, int n, char *X, char *Y, int b[][100] ) {/*計算最長公共子序列的長度*/int num[100][100];int i,j;int sum;/*清零*/for( i=0 ; i<=m ; i++ ){for( j=0 ; j<=n ; j++ ){num[i][j]=0;b[i][j]=0;}} /* 遞歸結構-動態規劃并輸出 */for( i=1 ; i<=m ; i++ ){ for( j=1 ; j<=n ; j++ ){if( X[i]==Y[j] ) {num[i][j]=num[i-1][j-1]+1;b[i][j]=1;}else if( num[i-1][j]>num[i][j-1] ) {num[i][j]=num[i-1][j];b[i][j]=2;}else if( num[i-1][j]<num[i][j-1] ){num[i][j]=num[i][j-1];b[i][j]=3;}else {num[i][j]=num[i][j-1];b[i][j]=4;}} }sum = num[m][n];printf("最長公共子序列的長度：%d\n",sum);//輸出c[m][n]表printf("\n");for(i=0;i<=m;i++){for(j=0;j<=n;j++){printf("%d ",num[i][j]);}printf("\n");}//輸出b[m][n]表printf("\n");for(i=0;i<=m;i++){for(j=0;j<=n;j++){printf("%d ",b[i][j]);}printf("\n");}return sum; }

第二個DisplayLSC函數是通過b[m][n]遞歸計算所有最長公共子序列,并存儲至result數組中.

//定義全局變量用于保存結果result 結果個數保存為count char result[100]; int count=0;//函數：計算所有最長公共子序列 //參數：m字符串X的長度 n字符串Y的長度 b標志數組 current_len當前長度 max_len最長公共子序列長度 void DisplayLSC(int i,int j,char *X,int b[][100],int current_len,int max_len) {int s;//采用遞歸的算法求解所有長度if(i==0 || j==0) //為0時輸出結果并返回{for(s=0;s<max_len;s++){printf("%c ",result[s]);}printf("\n");count++;return;}if(b[i][j]==1){current_len--;result[current_len]=X[i];DisplayLSC(i-1,j-1,X,b,current_len,max_len);}else{if(b[i][j]==2){DisplayLSC(i-1,j,X,b,current_len,max_len);}else{if(b[i][j]==3){DisplayLSC(i,j-1,X,b,current_len,max_len);}else{DisplayLSC(i,j-1,X,b,current_len,max_len);DisplayLSC(i-1,j,X,b,current_len,max_len);}}} }

3.結果

最后輸出的結果如下圖所示:

???? ?

希望該文章對大家有所幫組,同時該文章參考了王曉東的《計算機算法設計與分析》,并引用了自己學校的PPT動態規劃內容.同時感謝夢醒瀟湘love博主的文章,希望大家也可以去見解該文章.
http://blog.chinaunix.net/uid-26548237-id-3374211.html
文章主要是對自己以前學過的知識的鞏固以記錄,如果有錯誤或不足之處,希望大家海涵.
(By:Eastmount 2013-11-5 中午3點http://blog.csdn.net/eastmount/)

總結

以上是生活随笔為你收集整理的算法知识之最长公共子序列问题(动态规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

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