问题：
最长公共子序列就是寻找两个给定序列的子序列，该子序列在两个序列中以相同的顺序出现，但是不必要是连续的。
例如序列X=ABCBDAB，Y=BDCABA。序列BCA是X和Y的一个公共子序列，但是不是X和Y的最长公共子序列，子序列BCBA是X和Y的一个LCS，序列BDAB也是。
思路：
1、最简单的方法就是暴力枚举。
先列举X所有的子序列，然后检查是否为Y的子序列，并记录最长的子序列。当该方法复杂度太高，假设X的长度为m，则X的子序列个数为2^m，指数级的复杂度是不实际的。
2、动态规划思想。
设X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>为两个序列，LCS(Xm,Yn)表示以Xm结尾的字符串和以Yn结尾的字符串的一个最长公共子序列，可以看出
如果xm=yn，则LCS ( Xm,Yn ) = xm + LCS ( Xm-1,Yn-1 )。
如果xm!=yn，则LCS( Xm,Yn )= max{ LCS ( Xm-1, Yn ), LCS ( Xm, Yn-1 ) }
最长公共子序列长度：
状态转移方程：
初始状态：dp[i][j]=0 if i==0 || j==0
转移方程：dp[i][j] = dp[i-1][j-1] + 1 if (X[i-1]==Y[j-1])
dp[i][j] = max ( dp[i-1][j], dp[i][j-1] ) if (X[i-1]!=Y[j-1])
最长公共子序列：
通过状态转移方程，可以逆推出最长子序列，如果x[i-1]==y[j-1] && dp[i][j]==dp[i-1][j-1]+1，则x[i-1]为最长子序列的元素，否则如果x[i-1]==y[j-1] && dp[i-1][j]>dp[i][j-1]，则i--，否则j--，这样就得到一个倒序的最长子序列，具体见参考代码。
复杂度分析：
上述思路的时间复杂度为O(m*n)，空间复杂度也为O(m*n);
dp[i][j] = dp[i-1][j-1] + 1 if (X[i-1]==Y[j-1])
dp[i][j] = max ( dp[i-1][j], dp[i][j-1] ) if (X[i-1]!=Y[j-1])
从状态转移方程可以看到，如果只求最长公共子序列长度的话，每一次转移的时候只与前一状态有关，因此空间复杂度可以从m*n降为2*n，只保存当前和前一状态，时间复杂度不变。
代码：
#include <iostream>
#include <vector> using namespace std; int LCS(char *str1,int len1,char *str2,int len2){
// calculate length of LCS
vector<vector<int> > dp(len1+,vector<int>(len2+,));
for(int i=;i<=len1;i++){
for(int j=;j<=len2;j++){
if(i== || j==)
dp[i][j]=;
else{
if(str1[i-]==str2[j-])
dp[i][j]=dp[i-][j-]+;
else
dp[i][j]=max(dp[i-][j],dp[i][j-]);
}
}
}
// record the LCS
int len=dp[len1][len2];
char lcsArr[len];
lcsArr[len]='\0';
int i=len1,j=len2;
while(i && j){
if(str1[i-]==str2[j-] && dp[i][j]==dp[i-][j-]+){
lcsArr[--len]=str1[i-];
i--;
j--;
}
else if(str1[i-]!=str2[j-] && dp[i-][j]>dp[i][j-])
i--;
else
j--;
} cout<<"Length of LCS is: "<<len<<endl;
cout<<"SubSequency of LCS is: "<<lcsArr<<endl; return dp[len1][len2];
} int main()
{
char str1[]="abcd";
char str2[]="bd";
int len1=sizeof(str1)/sizeof(str1[])-;
int len2=sizeof(str2)/sizeof(str2[])-;
cout << LCS(str1,len1,str2,len2) << endl;
return ;
}
int LCS2(char *str1,int len1,char *str2,int len2){
// only to calculate length of LCS
// reduce the space complexity from m*n to 2*n
vector<vector<int> > dp(,vector<int>(len2+,));
int k;
for(int i=;i<=len1;i++){
k=i&;
for(int j=;j<=len2;j++){
if(j==)
dp[k][j]=;
else{
if(str1[i-]==str2[j-])
dp[k][j]=dp[-k][j-]+;
else
dp[k][j]=max(dp[-k][j],dp[k][j-]);
}
}
}
cout<<"Length of LCS is: "<<dp[k][len2]<<endl;
return dp[k][len2];
}