動态規劃算法與分治算法類似，基本思想都是将待解問題分解成若幹個子問題，先求解子問題，然後根據子問題的解得到原問題的解。
在用分治法求解的時候有些子問題被重複計算了很多次。
動态規劃算法則有效的将子問題的解儲存起來，在需要的時候再找出來使用，這樣就避免了大量的重複計算。
為了達到這樣的目的，可以用一個表來記錄所有已經解決的子問題的答案。
最長公共子序列問題：
一個給定序列的子序列是在該序列中删除若幹元素之後得到的自序列。确切的說
若給定序列 ABCDEFG , 則 ABC , CDE, ABCDEFG 等都是其自序列，不一定需要連續的
最長公共子序列也就是給定兩個序列 X , Y，求這兩個最長的相同的子序列。
最長公共子序列的結構有如下表示： 一：最長公共子序列的結構 設序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一個最長公共子序列Z=<z1, z2, …, zk>，則： 1> 若 xm=yn，則 zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列； 2> 若 xm≠yn且 zk≠xm ，則 Z是 Xm-1和 Y的最長公共子序列； 3> 若 xm≠yn且 zk≠yn ，則 Z是 X和 Yn-1的最長公共子序列； 其中Xm-1=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。
二： 子問題的遞歸結構
由最長公共子序列問題的最優子結構性質可知，要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最長公共子序列，可按以下方式遞歸地進行：當xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然後在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當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和Yj的最長公共子序列的長度。其中Xi=<x1, x2, …, xi>，Yj=<y1, y2, …, yj>。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故c[i,j]=0。其他情況下，由定理可建立遞歸關系如下：
三： 計算最優值
直接利用上節節末的遞歸式，我們将很容易就能寫出一個計算c[i,j]的遞歸算法，但其計算時間是随輸入長度指數增長的。由于在所考慮的子問題空間中，總共隻有θ(m*n)個不同的子問題，是以，用動态規劃算法自底向上地計算最優值能提高算法的效率。
計算最長公共子序列長度的動态規劃算法LCSLength(xlen,ylen,x,y,c,b);以序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>作為輸入。輸出兩個數組c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存儲Xi與Yj的最長公共子序列的長度，bi,j]記錄訓示c[i,j]的值是由哪一個子問題的解達[到的，這在構造最長公共子序列時要用到。最後，X和Y的最長公共子序列的長度記錄于c[m,n]中。
void LCSLength(int xlen, int ylen, char x[] , char y[], int c[][MAXLEN] , int b[][MAXLEN]) {
int i , j;
/*
c[i][j]代表目前X1X2...Xi和Y1Y2...Yj序列的公共子序列的長度
因為c[i][0]和c[0][j]都代表其中一個序列長度為0，是以公共自序列長度為0
*/
for(i=0 ; i<xlen ; i++) {
c[i][0] = 0;
}
for(j=0 ; j<ylen ; j++) {
c[0][j] = 0;
}
// 根據不同的情況計算c[i][j]的值
for(i=1 ; i<=xlen ; i++) {
for(j=1 ; j<=ylen;j++) {
if(x[i-1] == y[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
} else if(c[i-1][j] > c[i][j-1]) { // 在c中也即為上側
c[i][j] = c[i-1][j];
b[i][j] = 2;
} else { // 在c中也即為左側
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
}
由算法LCSLength計算得到的數組b可用于快速構造序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最長公共子序列。首先從b[m,n]開始，沿着其中的箭頭所指的方向在數組b中搜尋。
- 當b[i,j]中遇到"↖"時（意味着xi=yi是LCS的一個元素），表示Xi與Yj的最長公共子序列是由Xi-1與Yj-1的最長公共子序列在尾部加上xi得到的子序列；
- 當b[i,j]中遇到"↑"時，表示Xi與Yj的最長公共子序列和Xi-1與Yj的最長公共子序列相同；
- 當b[i,j]中遇到"←"時，表示Xi與Yj的最長公共子序列和Xi與Yj-1的最長公共子序列相同。
這種方法是按照反序來找LCS的每一個元素的。由于每個數組單元的計算耗費Ο(1)時間，算法LCSLength耗時Ο(mn)。
四：構造最長公共子序列
下面的算法GetLCS實作根據b的内容列印出Xi與Yj的最長公共子序列。通過算法的調用LCS(b,X,length[X],length[Y])，便可列印出序列X和Y的最長公共子序列。
void GetLCS(int xlen, int ylen, char x[],int b[][MAXLEN]) {
// 因為b[i][j]記錄了c[i][j]是從那一種子問題的解得到的
if(xlen == 0 || ylen == 0) {
return ;
}
if(b[xlen][ylen] == 1) {
GetLCS(xlen-1,ylen-1,x,b);
printf("%c",x[xlen-1]);
} else if(b[xlen][ylen] == 2) {
GetLCS(xlen-1,ylen,x,b);
} else {
GetLCS(xlen,ylen-1,x,b);
}
}
在算法LCS中，每一次的遞歸調用使i或j減1，是以算法的計算時間為 O (m+n)。
例如，設所給的兩個序列為X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS計算出的結果如下圖所示：
我來說明下此圖（參考算法導論）。在序列X={A，B，C，B，D，A，B}和 Y={B，D，C，A，B，A}上，由LCSLength計算出的表c和b。第i行和第j列中的方塊包含了c[i，j]的值以及指向b[i，j]的箭頭。在c[7,6]的項4，表的右下角為X和Y的一個LCS<B，C，B，A>的長度。對于i，j>0，項c[i，j]僅依賴于是否有xi=yi，及項c[i-1，j]和c[i，j-1]的值，這幾個項都在c[i，j]之前計算。為了重構一個LCS的元素，從右下角開始跟蹤b[i，j]的箭頭即可，這條路徑标示為陰影，這條路徑上的每一個“↖”對應于一個使xi=yi為一個LCS的成員的項（高亮标示）。
是以根據上述圖所示的結果，程式将最終輸出：“B C B A”。
全部代碼如下：
#include<stdio.h>
#include<string.h>
#define MAXLEN 30
void LCSLength(int xlen, int ylen, char x[] , char y[], int c[][MAXLEN] , int b[][MAXLEN]) {
int i , j;
/*
c[i][j]代表目前X1X2...Xi和Y1Y2...Yj序列的公共子序列的長度
因為c[i][0]和c[0][j]都代表其中一個序列長度為0，是以公共自序列長度為0
*/
for(i=0 ; i<xlen ; i++) {
c[i][0] = 0;
}
for(j=0 ; j<ylen ; j++) {
c[0][j] = 0;
}
// 根據不同的情況計算c[i][j]的值
for(i=1 ; i<=xlen ; i++) {
for(j=1 ; j<=ylen;j++) {
if(x[i-1] == y[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
} else if(c[i-1][j] > c[i][j-1]) { // 在c中也即為上側
c[i][j] = c[i-1][j];
b[i][j] = 2;
} else { // 在c中也即為左側
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
}
void GetLCS(int xlen, int ylen, char x[],int b[][MAXLEN]) {
// 因為b[i][j]記錄了c[i][j]是從那一種子問題的解得到的
if(xlen == 0 || ylen == 0) {
return ;
}
if(b[xlen][ylen] == 1) {
GetLCS(xlen-1,ylen-1,x,b);
printf("%c",x[xlen-1]);
} else if(b[xlen][ylen] == 2) {
GetLCS(xlen-1,ylen,x,b);
} else {
GetLCS(xlen,ylen-1,x,b);
}
}
int main() {
int i , j;
char x[MAXLEN] , y[MAXLEN];
int c[MAXLEN][MAXLEN] , b[MAXLEN][MAXLEN];
// m記錄X序列的長度，n記錄Y序列的長度
int xlen , ylen;
// 分别輸入X,Y序列
printf("請輸入X序列:\n");
scanf("%s",x);
xlen = strlen(x);
printf("請輸入y序列:\n");
scanf("%s",y);
ylen = strlen(y);
LCSLength(xlen,ylen,x,y,c,b);
printf("數組c的結果為：\n");
for(i=1;i<=xlen;i++) {
for(j=1;j<=ylen;j++) {
printf("%3d",c[i][j]);
}
printf("\n");
}
printf("數組b的結果為：\n");
for(i=1;i<=xlen;i++) {
for(j=1;j<=ylen;j++) {
printf("%3d",b[i][j]);
}
printf("\n");
}
printf("公共子序列長度為：%d\n", c[xlen][ylen]);
printf("公共子序列為：");
GetLCS(xlen,ylen,x,b);
printf("\n");
return 0;
}
以上原理述說和圖檔參考自： http://blog.csdn.net/v_july_v/article/details/6695482