一、動態規劃算法與分治法的異同

相同點：

A、二者均是將待求解的問題分成若干子問題來求解。? ? ? ? ??

B、二者在編寫代碼的時候，都要用到遞歸。

不同點：

A、分治法求解的問題，在將問題分成若干子問題之后，其子問題之間是獨立存在的，沒有相互關聯。而動態規劃問題劃分后得到的子問題之間相互關聯。

B、動態規劃問題在求解時需要一個表來記錄已解決的子問題的答案，從而避免大量的重復計算。動態規劃算法適合用于解最優化問題。這就表明這類最優化問題可能有很多解，但不一定都是最優解，而利用本算法找出的解可能還是眾多最優解里的一個

二、最優解問題結構性質

最優子結構：當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。

重疊子問題：在用遞歸算法自頂向下解決問題的時候，每次產生的子問題并不總是新問題，有些子問題被反復計算。動態規劃算法正式利用這種子問題的重疊性質，對每個子問題只解一次，并將其保存在表格中。

從一般意義上來講，問題所具有的這兩個重要性質是該問題可用動態規劃算法求解的基本要素。

三、動態規劃問題分析及解決步驟

A、找出最優解的性質，刻畫其結構特征。

B、遞歸定義最優值

C、自底向上計算最優值（最優值只是一個結果，最優解是一個過程）

D、根據得到的信息構造最優解（A-C是動態規劃算法的進本步驟，此步在需要求出問題的最優解時才需執行）

好了，有了上面動態規劃的基礎知識后，我們開始本文的“重頭戲”——最長公共子序列。

四、問題描述（問題大意）

子序列：一個給定序列中，刪除若干元素后得到的序列，就是該序列的子序列。

公共子序列：如果有兩個序列按照上述步驟之后得到的子序列相同，那么這個子序列被稱為這兩個序列的公共子序列。

例：有如下兩個序列

X={A、B、C、B、D、A、B}，Y={B、D、C、A、B、A}

則序列Z={B、C、A}就是二者的公共子序列，那么什么是最長的公共子序列，大家應該知道了吧？

在這里需要說明的是：一個長度為n的序列，它一共有2的n次方個子序列，有(2^n?– 1)個非空子序列。大家需要注意的是，這里說的是序列，和原來的順序有關聯，而不是高中所學無序的集合。

下面將按照動態規劃算法設計的步驟來設計解決此問題的算法

1、問題結構

?上述證明之后，本問題具有最優子結構性質。

2、遞歸結構

要找出X={x1,x2,...,xm}和Y={y1,y2,...,yn}的最長公共子序列，可按照以下方式遞歸：

A、當Xm=Yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上Xm（Xm=Yn），即可得X、Y的最長公共子序列。

B、當Xm！=Yn時，則得解決兩個子問題：Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列，二者中較長者即為X和Y的最長公共子序列。

由這個遞歸結構來看，此問題具有子問題重疊性質，例如：在計算X和Y的最長公共子序列時，可能要計算X和Yn-1及Xm-1和Y的最長公共子序列，這兩個子問題都包含一個公共子問題，即要計算Xm-1和Yn-1的最長公共子序列。

首先建立子問題最優值的遞歸關系，用從c[i][j]記錄序列Xi和Yi的最長公共子序列的長度。其中，Xi={x1,x2,...,xi};Yj={y1,y2,...,yj}

當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，所以此時c[i][j]=0;

其他情況：

A、i>0;j=0時,c[i][j]=0;

B、i,j>0;Xi=Yj時，c[i][j]=c[i-1][j-1]+1

C、i,j>0;Xi!=Yj時，c[i][j]=max{c[i][j-1],c[i-1][j]}

3、計算最優值

直接利用上述遞歸式，寫出代碼。其中X，Y是輸入的兩個序列， ，b[i][j]記錄c[i][j]的值是由哪個子問題的解得來的，這在構造最長公共子序列時要用到。

void LCSLength(int m,int n,char x[],char y[],int c[][50],int b[][50])
{int i,j;for(i=1;i<=m;i++)//當j=0時，c[i][j]=0c[i][0]=0;for(j=1;j<=n;j++)//當i=0時，c[i][j]=0c[0][j]=0;for(i=1;i<=m;i++)//對最長公共子序列的長度進行記錄for(j=1;j<=n;j++){if(x[i]==y[j])//Xi=Yj的情況{c[i][j]=c[i-1][j-1]+1;//c[i][j]存儲Xi和Yj的最長公共子序列的長度b[i][j]=1; //斜向上           //b[i][j]記錄c[i][j]的值是由哪個子問題的解得來的}else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;//豎直向上}else{c[i][j]=c[i][j-1];b[i][j]=3;//水平向左}}
}

4、構造最長公共子序列

用二維數組b快速構造序列X和Y的最長公共子序列。首先從b[m][n]開始，依照其值在數組b中搜索。

A、當在b[i][j]=1時，表示Xi和Yi的最長公共子序列是由Xi-1和Yi-1的最長公共子序列在尾部加上Xi所得到的。

B、當在b[i][j]=2時，表示Xi和Yj的最長公共子序列與Xi-1和Yj的最長公共子序列相同。

C、當在b[i][j]=3時，表示Xi和Yj的最長公共子序列與Xi和Yj-1的最長公共子序列相同。

如此，將最長公共子序列打印出來。代碼如下：

void LCS(int i,int j,char x[], int b[][50])
{if(i==0||j==0)return;if(b[i][j]==1)//表示Xi和Yi的最長公共子序列是由Xi-1和Yi-1的最長公共子序列在尾部加上Xi所得到的{//b[i][j]==1時，表示左斜45°向上，也即這個時候對應的字母時LCS中的一個。LCS(i-1,j-1,x,b);cout<<x[i]<<" ";}else if(b[i][j]==2)//表示Xi和Yj的最長公共子序列與Xi-1和Yj的最長公共子序列相同。LCS(i-1,j,x,b);else//表示Xi和Yj的最長公共子序列與Xi和Yj-1的最長公共子序列相同。LCS(i,j-1,x,b);
}

所以，上述的所有步驟轉變為完整代碼如下：

#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
int c[50][50];
int b[50][50];
char x[1000];//存放X字符串
char y[1000];//存放Y字符串
void LCSLength(int m,int n,char x[],char y[],int c[][50],int b[][50])
{int i,j;for(i=1;i<=m;i++)//當j=0時，c[i][j]=0c[i][0]=0;for(j=1;j<=n;j++)//當i=0時，c[i][j]=0c[0][j]=0;for(i=1;i<=m;i++)//對最長公共子序列的長度進行記錄for(j=1;j<=n;j++){if(x[i]==y[j])//Xi=Yj的情況{c[i][j]=c[i-1][j-1]+1;//c[i][j]存儲Xi和Yj的最長公共子序列的長度b[i][j]=1; //斜向上           //b[i][j]記錄c[i][j]的值是由哪個子問題的解得來的}else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;//豎直向上}else{c[i][j]=c[i][j-1];b[i][j]=3;//水平向左}}
}
void LCS(int i,int j,char x[], int b[][50])
{if(i==0||j==0)return;if(b[i][j]==1)//表示Xi和Yi的最長公共子序列是由Xi-1和Yi-1的最長公共子序列在尾部加上Xi所得到的{//b[i][j]==1時，表示左斜45°向上，也即這個時候對應的字母時LCS中的一個。LCS(i-1,j-1,x,b);cout<<x[i]<<" ";}else if(b[i][j]==2)//表示Xi和Yj的最長公共子序列與Xi-1和Yj的最長公共子序列相同。LCS(i-1,j,x,b);else//表示Xi和Yj的最長公共子序列與Xi和Yj-1的最長公共子序列相同。LCS(i,j-1,x,b);
}
int main()
{int xn,yn;//XY字符串的大小cout<<"請輸入X集合的元素個數："<<endl;cin>>xn;cout<<"請輸入X集合的元素："<<endl;int i=0;//用于循環輸入X和Y的字符串for(i=1;i<=xn;i++)cin>>x[i];cout<<"請輸入y集合的元素個數："<<endl;cin>>yn;cout<<"請輸入y集合的元素："<<endl;for(i=1;i<=yn;i++)cin>>y[i];LCSLength(xn,yn,x,y,c,b);cout << "X和Y的最長公共子序列為：";LCS(xn,yn,x,b);cout << endl;int j = 0;int m = 0;printf("b[i][j]中的數字：\n");for (i = 0; i <=xn; i++)for (j = 0; j <= yn; j++){ printf("%d ", b[i][j]);m++;if (m == xn){m = 0;printf("\n");}}m = 0;printf("c[i][j]中的數字：\n");for (i = 0; i <= xn; i++)for (j = 0; j <=yn; j++){printf("%d ", c[i][j]);m++;if (m == xn){printf("\n");m = 0;}}	system("pause");return 0;
}

把c[i][j]和b[i][j]對應起來之后，得到下圖：

從下圖中可以看出，用二維數組b[i][j]中的信息可以構建出X和Y的一個最長公共子序列。從b[xn][yn]開始，沿著橘黃色的箭頭方向追蹤：

A、b[i][j]等于1時，左斜45°向上跳，并且起跳的字母就是LCS的一個成員

B、b[i][j]等于2時，豎直向上跳。

C、b[i][j]等于3時，水平向左跳。

參考：《計算機算法設計與分析·第五版 》王曉東編著