著實(shí)是有好幾天沒有動手寫寫自己的博客了。這些天感覺自己是被別人的事情搞的一團(tuán)糟，結(jié)果自己反倒是幫不上什么忙的。還是算了吧，先將自己的東西好好的忙好，畢竟還是得自己有能力才能夠幫到別人的，沒辦法，物競天擇適者生存。

好了，ACM也是告了一個段落，結(jié)果等來等去等到了算法課，最終是讓自己失望萬分，還是趕緊的重操舊業(yè)把，好好努力，爭取讓自己搞出一點(diǎn)成績來，即使最后是失敗了，也是雖敗猶榮，亮劍精神嘛。

今天研究的問題是最長公共子序列，著實(shí)由于基礎(chǔ)不扎實(shí)，網(wǎng)上找了一篇博客，現(xiàn)在將它的解決方案列舉出來：

方法一：枚舉法

主要是將第一個串的所有的子序列全部都列舉出來，然后和第二個串進(jìn)行匹配，這個屬于暴力破解法。

方法二：動態(tài)規(guī)劃

這里樓主采用的是矩陣的方式來實(shí)現(xiàn)的，也就是二維數(shù)組。

先是計算最長公共子序列的長度，然后是根據(jù)長度回溯出最長公共子序列。

現(xiàn)有兩個序列X={x₁,x₂,x_3，...x_i}，Y={y₁,y₂,y_3，....，y_i}，

設(shè)一個C[i,j]: 保存X_i與Y_j的LCS的長度。

遞推方程為：

不知道大家看懂了沒？動態(tài)規(guī)劃的一個重要性質(zhì)特點(diǎn)就是解決“子問題重疊”的場景，可以有效的避免重復(fù)計算，根據(jù)上面的

公式其實(shí)可以發(fā)現(xiàn)C[i,j]一直保存著當(dāng)前(X_i,Y_i)的最大子序列長度。

?

1 #include<stdio.h> 2 #include<string.h> 3 char a[30],b[30]; 4 int lena,lenb; 5 int LCS(int,int);　　///兩個參數(shù)分別表示數(shù)組a的下標(biāo)和數(shù)組b的下標(biāo) 6 7 int main() 8 { 9 strcpy(a,"ABCBDAB"); 10 strcpy(b,"BDCABA"); 11 lena=strlen(a); 12 lenb=strlen(b); 13 printf("%d\n",LCS(0,0)); 14 return 0; 15 } 16 17 int LCS(int i,int j) 18 { 19 if(i>=lena || j>=lenb) 20 return 0; 21 if(a[i]==b[j]) 22 return 1+LCS(i+1,j+1); 23 else 24 return LCS(i+1,j)>LCS(i,j+1)? LCS(i+1,j):LCS(i,j+1); 25 }

?下面的這個是根據(jù)公式優(yōu)化出來的代碼：

1 #include <iostream> 2 #include <string> 3 #include<stdio.h> 4 #include<string.h> 5 6 7 char a[500],b[500]; 8 char num[501][501]; ///記錄中間結(jié)果的數(shù)組 9 char flag[501][501]; ///標(biāo)記數(shù)組，用于標(biāo)識下標(biāo)的走向，構(gòu)造出公共子序列 10 void LCS(); ///動態(tài)規(guī)劃求解 11 void getLCS(); ///采用倒推方式求最長公共子序列 12 13 using namespace std; 14 15 int main() 16 { 17 int i; 18 strcpy(a,"zhangjie"); 19 strcpy(b,"hetongkang"); 20 memset(num,0,sizeof(num)); 21 memset(flag,0,sizeof(flag)); 22 LCS(); 23 printf("%d\n",num[strlen(a)][strlen(b)]); 24 getLCS(); 25 return 0; 26 } 27 28 void LCS() 29 { 30 int i,j; 31 for(i=1;i<=strlen(a);i++) 32 { 33 for(j=1;j<=strlen(b);j++) 34 { 35 if(a[i-1]==b[j-1]) ///注意這里的下標(biāo)是i-1與j-1 36 { 37 num[i][j]=num[i-1][j-1]+1; 38 flag[i][j]=1; ///斜向下標(biāo)記 39 } 40 else if(num[i][j-1]>num[i-1][j]) 41 { 42 num[i][j]=num[i][j-1]; 43 flag[i][j]=2; ///向右標(biāo)記 44 } 45 else 46 { 47 num[i][j]=num[i-1][j]; 48 flag[i][j]=3; ///向下標(biāo)記 49 } 50 } 51 } 52 } 53 54 void getLCS() 55 { 56 57 char res[500]; 58 int i=strlen(a); 59 int j=strlen(b); 60 int k=0; ///用于保存結(jié)果的數(shù)組標(biāo)志位 61 while(i>0 && j>0) 62 { 63 if(flag[i][j]==1) ///如果是斜向下標(biāo)記 64 { 65 res[k]=a[i-1]; 66 k++; 67 i--; 68 j--; 69 } 70 else if(flag[i][j]==2) ///如果是斜向右標(biāo)記 71 j--; 72 else if(flag[i][j]==3) ///如果是斜向下標(biāo)記 73 i--; 74 } 75 76 for(i=k-1;i>=0;i--) 77 printf("%c",res[i]); 78 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/tianxia2s/p/3998817.html

總結(jié)

以上是生活随笔為你收集整理的2014年9月28日 18:35:01的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。