1、基本概念
一個給定序列的子序列就是該給定序列中去掉零個或者多個元素的序列。形式化來講就是：給定一個序列X={x1，x2，……，xm}，另外一個序列Z={z1、z2、……，zk}，如果存在X的一個嚴格遞增小标序列<i1，i2……，ik>，使得對所有j=1,2，……k，有xij = zj，則Z是X的子序列。例如：Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一個子序列，相應的小标為<2,3,5,7>。從定義可以看出子序列直接的元素不一定是相鄰的。
公共子序列：給定兩個序列X和Y，如果Z既是X的一個子序列又是Y的一個子序列，則稱序列Z是X和Y的公共子序列。例如：X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}，則序列{B,C,A}是X和Y的一個公共子序列，但不不是最長公共子序列。
最長公共子序列（LCS）問題描述：給定兩個序列X={x1，x2，……，xm}和Y={y1，y2，……，yn}，找出X和Y的最長公共子序列。
2、動态規劃解決過程
1）描述一個最長公共子序列
如果序列比較短，可以采用蠻力法枚舉出X的所有子序列，然後檢查是否是Y的子序列，并記錄所發現的最長子序列。如果序列比較長，這種方法需要指數級時間，不切實際。
LCS的最優子結構定理：設X={x1，x2，……，xm}和Y={y1，y2，……，yn}為兩個序列，并設Z={z1、z2、……，zk}為X和Y的任意一個LCS，則：
（1）如果xm=yn，那麼zk=xm=yn，而且Zk-1是Xm-1和Yn-1的一個LCS。
（2）如果xm≠yn，那麼zk≠xm蘊含Z是是Xm-1和Yn的一個LCS。
（3）如果xm≠yn，那麼zk≠yn蘊含Z是是Xm和Yn-1的一個LCS。
定理說明兩個序列的一個LCS也包含兩個序列的字首的一個LCS，即LCS問題具有最優子結構性質。
2）一個遞歸解
根據LCS的子結構可知，要找序列X和Y的LCS，根據xm與yn是否相等進行判斷的，如果xm=yn則産生一個子問題，否則産生兩個子問題。設C[i,j]為序列Xi和Yj的一個LCS的長度。如果i=0或者j=0，即一個序列的長度為0，則LCS的長度為0。LCS問題的最優子結構的遞歸式如下所示：
3）計算LCS的長度
采用動态規劃自底向上計算解。書中給出了求解過程LCS_LENGTH，以兩個序列為輸入。将計算序列的長度儲存到一個二維數組C[M][N]中，另外引入一個二維數組B[M][N]用來儲存最優解的構造過程。M和N分别表示兩個序列的長度。該過程的僞代碼如下所示：
由僞代碼可以看出LCS_LENGTH運作時間為O(mn)。
4）構造一個LCS
根據第三步中儲存的表b建構一個LCS序列。從b[m][n]開始，當遇到'\'時，表示xi=yj，是LCS中的一個元素。通過遞歸即可求出LCS的序列元素。書中給出了僞代碼如下所示：
3、程式設計實作
現在采用C++語言實作上述過程，例如有兩個序列X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}，求其最長公共子序列Z。完整程式如下所示：
運作結果：
