最长公共子序列的长度（动态规划）
给定X = 3, 0, 3, 8, 4, 4
　　Y= 4, 3, 8, 3, 0, 4
求X和Y的最长公共子序列的长度。
[解决办法]
int len[8][6] = {0}; //记录序列1的 i 和序列2的 j 的最长公共子序列的长度
int flag[8][6] = {0}; //记录在i和j处的选择,为后面输出最长子序列

int LCS()
{
int i, j;

for(i=1; i<m; i++)
{
for(j=1; j<n; j++)
{
if(X[i] == Y[j])
{
len[i][j] = len[i-1][j-1] + 1;
flag[i][j] = 0;
}
else if(len[i-1][j] >= len[i][j-1])
{
len[i][j] = len[i-1][j];
flag[i][j] = 1;
}
else
{
len[i][j] = len[i][j-1];
flag[i][j] = 2;
}
}
}
return len[m-1][n-1];
}

void printLCS(int i, int j)
{
if(i==0
[解决办法]
j==0)
return;
if(flag[i][j] == 0)
{
printLCS(i-1, j-1);
printf("%c ", X[i]);
}
else
{
if(flag[i][j] == 1)
printLCS(i-1, j);
else
printLCS(i, j-1);
}
}

int main()
{
printf("Longest Common Sequence Length: %d\n", LCS());
printLCS(m-1, n-1);
printf("\n");
return 0;
}
[解决办法]
DP主要就是一个递推公式。
其实现还是比较简单的，填表法，需要记录解的过程，这样才能在之后找到解。

#include <iostream>
#include <string>
#include <stack>
using namespace std;

/*
DP的核心公式：
if xi = yj:
  LCS(xi,yj)=LCS(xi-1,yj-1)+1;
else  
  LCS(xi,yj)=max(LCS(xi-1,yj),LCS(xi,yj-1)).
*/

int LCS_DP( string x, string y )
{
int xlen=x.size();
int ylen=y.size();
//int *lcs = new int[(xlen+1)*(ylen+1)]();
int **lcs = new int*[xlen+1];
int **path = new int*[xlen+1];

for( int i=0; i<=xlen; i++){
lcs[i] = new int[ylen+1]();
path[i] = new int[ylen+1]();
}

for( int k=1; k<=xlen+ylen;k++){
for( int i=1; i<=xlen; i++){
for( int j=1; j<=k-i&&j<=ylen; j++){
if(x[i-1]==y[j-1]){
lcs[i][j] = lcs[i-1][j-1]+1;
path[i][j] = 1;//1表示两个字符相等
}
else{
int a=lcs[i-1][j];
int b=lcs[i][j-1];
lcs[i][j] = a>b?a:b;
path[i][j] = a>b?2:3;           //2表示来自y，3表示来自x
}
}
}
}

stack<char> stk;
for( int i=xlen,j=ylen; i>0&&j>0; )
{
if( path[i][j] == 1 ){ 
 
stk.push( x[i-1] );
i--;j--;
}
if( path[i][j] == 2 ){
i--;
}
if( path[i][j] == 3 ){
j--;
}
}

cout <<"The Longest Common Sequence Length: " <<lcs[xlen][ylen]<<endl;
cout <<"The Longest Common Sequence is:"<<endl;
while( !stk.empty() ){
cout << stk.top();
stk.pop();
}

return lcs[xlen][ylen];
}

int main()
{
string a,b;
cout << "Input two string: " <<endl;
cin>> a >> b;
LCS_DP( a, b);
return 0;
}