動态規劃與分治方法類似，都是通過組合子問題來求解原問題。分治法将問題分為互不相交的子問題，遞歸的求解子問題，再将他們的解組合起來，求出原問題的解。相反的，動态規劃用于子問題重疊的情況，即不同的子問題具有公共的子子問題（子子問題為将子問題分為更小的問題）。
1.簡介
如果Z既是X的子序列，又是其它字元序列的子序列，而且Z是這些字元序列中最長的子序列，則稱Z為這些字元序列的最長公共子序列（簡稱LCS)設計程式。
2.實作
子序列與子串不同，子串要求取連續的字元，而子序列不要求連續的字元，但必須按順序取。
以兩個字元串X<X1,X2,X3------Xn> ,Y<Y1,Y2,Y3------Yn>為例，尋找兩個字元串X,Y中的最長公共子序列。
①窮舉法：
窮舉法，顧名思義，依次取X的子序列，Y的子序列來比較，而X的子序列有2 個，Y的子序列有 個，依次比較，這種算法的時間複雜度為O（2 * ），當m,n的數值比較大（即字元串X,Y較長）時，時間複雜度是非常大的。
②動态規劃法：
将待求解的問題分解為若幹個子問題，按順序求解子階段，前一子問題的解，為後一子問題的求解提供了有用的資訊。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丢棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。
對于求解X,Y兩個字元串的最長公共子序列的問題，引入一個數組c[m][n],用c[i][j]記錄字元串X[0]~X[i]與字元串Y[0]~Y[j]的LCS長度，引入一個數組b[m][n]，用b[i][j]記錄c[i][j]是由哪一個子問題求解得到的,填充’ ↑’，’← ’，’↖’。分别表示由上邊、左邊、左上的子問題求解得到。
矩陣的初始化：
數組c[m][n]初始化為0，然後按下邊的公式填充c[m][n]矩陣
下面讨論時，字元串X,Y的下标從0開始,是以 c[i][j] 所對應的字元為 X[i-1] , Y[j-1].
當i,或j等于0的時候，c[i][j]=0意思為：
矩陣第一行和第一列為空出來的，不做字元的比較，全部填充為0；
當i,j>0時：
c[i][j]=c[i-1][j-1]+1 意思為：
當字元 X[i-1] = Y[j-1] 時，此時的LCS長度等于上一個子問題，即 X[i-1] 與 Y[j-1] 的LCS 長度加一;b[i][j]填 充為“ ↖”。
c[i][j]=max{ c[i,j-1],c[i-1,j] } 意思為：
當字元 X[i-1] ≠ Y[j-1] 時，此時的LCS長度等于前邊的子問題取最優解，即 X[i-2] , Y[j-1] 與 X[i-1],Y[j-2] 的最大的LCS長度。b[i][j]填充“ ←”或“ ↑”。
填充結束後，填充效果如下圖，數組c[m][n]的值即為字元串X,Y的LCS長度。
輸出最長公共子序列：
根據b[m][n]的方向回溯，當箭頭方向為“↖”時，表示此處字元串X,Y所對應的字元相等，即可将其添加到temp字元串中，最後倒序輸出即可，也可以利用遞歸函數回溯輸出。
代碼如下：
#include<bits/stdc++.h>
using namespace std;
void LCS(string str1,string str2,int** &c,int** &b);
void print(string str1,int **b,int m,int n);
int main()
{
string str1,str2;
cin>>str1>>str2;
//兩個矩陣，c存放LCS長度，b存放方向
//b的方向表示：1表示左側，2表示上側，3表示左上
int **c,**b;
LCS(str1,str2,c,b);
print(str2,b,str2.length(),str1.length());
}
//LCS函數
void LCS(string str1,string str2,int** &c,int** &b)//c,b傳引用的目的是為了可以改變主函數中的數組
{
int len1 = str1.length(), len2 = str2.length();
//為c,b配置設定空間
c=new int*[len2+1];
b=new int*[len2+1];
for(int i=0;i<len2+1;i++)
{
c[i]=new int[len1+1];
b[i]=new int[len1+1];
}
//c,b初始化為0
for(int i=0;i<len2+1;i++)
{
for(int j=0;j<len1+1;j++)
{
b[i][j]=0;
c[i][j]=0;
}
}
//設定矩陣c,b
for(int i=1;i<len2+1;i++)
{
for(int j=1;j<len1+1;j++)
{
if(str1[j-1]==str2[i-1])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=3;
}
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]=1;
}
}
}
}
}
//回溯法輸出LCS序列
void print(string str1,int **b,int m,int n)
{
if(m!=0&&n!=0)
{
if(b[m][n]==3)
{
//cout<<str1[m-1]<<" ";//此處為倒序輸出
print(str1,b,m-1,n-1);//向左上回溯
cout<<str1[m-1]<<" ";//此處為正序輸出
}
else if(b[m][n]==2) print(str1,b,m,n-1);//向上回溯
else if(b[m][n]==1) print(str1,b,m-1,n);//向左回溯
}
}
運作結果如下：