1. 动态规划转移方程
两个字符串str1和str2,长度分别为（len1，len2)
dp[i][j]表示以两个字符串分别以第i和第j个字符结尾所能达到的公共子序列的长度, 假设i,j 下标从1开始到len1,len2, 则
if(str[i]=str[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=0;
0 ; i = 0或j= 0;
所以 dp = dp[i][j] = dp[i-1][j-1] + 1; i > 0且j> 0且ch1[i]= ch2[j];
dp[i][j]= 0; i > 0且j> 0且ch1[i]!= ch2[j];
2. 分析
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置.
下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
【注】：
具体方法如下：
令LEN=min(len1, len2)，依上述第二种矩阵生成原理，从第一行（列）起，由上（左）往下（右）依次生成得到各行（列）的数值，由于每一行（列）的数据的生成只需要通过两个母串的对比和借助上一行（列）的结果得到，因此除了当前行（列）的上一行（列），之前的行（列）的数据均可以被抛弃，因此，该算法只需要用于保存上一行（列）的计算结果的长为LEN的辅助数组空间和几个额外记录单元即可。（注：对当前行（列）计算结果的保存只需要对辅助数组做更新操作即可，这个就不用说啦，呵~）
参考：http://blog.sina.com.cn/s/blog_455b20c10100929m.html
3. 源代码：
方法1：时间复杂度O(n1*n2),空间复杂度O(n1*n2)
//求最长公共子序列
//构造二维空间
void LCS(char *str1,char *str2){
int len1,len2;
int **T;
int i,j;
int maxlen=0;
int end_flag=0;
len1=strlen(str1);
len2=strlen(str2);
T=new int*[len1];
for(i=0;i<len1;i++)
T[i]=new int[len2];
cout<<str1<<endl;
cout<<str2<<endl;
for(i=0;i<len1;i++){
for(j=0;j<len2;j++){
if(str1[i]==str2[j]){
if(i>0 && j>0)
T[i][j]=T[i-1][j-1]+1;// 长度为左上角元素值+1
else
T[i][j]=1;
if(maxlen<T[i][j]){
maxlen=T[i][j];// 存储最大长度
end_flag=i;// 存储最长公共字串的最后一个字符在str1中的位置
}
}
else
T[i][j]=0;
}
}
for(i=0;i<len1;i++){//输出矩阵结果
for(j=0;j<len2;j++){
cout<<setw(3)<<T[i][j]<<" ";
}
cout<<endl;
}
cout<<"maxle="<<maxlen<<endl;
if(maxlen==0)
cout<<"no common substring"<<endl;
else{
for(i=end_flag-maxlen+1;i<=end_flag;i++)
cout<<str1[i];
cout<<endl;
}
for(i=0;i<len1;i++)
delete [] T[i];
delete T;
}
方法2：时间复杂度O(n1*n2),空间复杂度O(min(n1,n2));
//method 2:
void LCS_OPT(char *str1,char *str2){
int len1,len2;
int *T;
int i,j;
int maxlen=0;
int end_flag=0;
char *small=str1;
char *big=str2;
len1=strlen(str1);
len2=strlen(str2);
if(len1<=len2)
T=new int[len1];
else{
T=new int[len2];
small=str2;
big=str1;
len1=strlen(big);
len2=strlen(small);
}
cout<<small<<endl;
cout<<big<<endl;
for(i=0;i<len1;i++){
for(j=len2-1;j>=0;j--){
if(small[j]==big[i]){
if(j>0 && i>0)
T[j]=T[j-1]+1;// 长度为左上角累计的元素值+1
else
T[j]=1;
if(maxlen<T[j]){
maxlen=T[j];// 存储最大长度
end_flag=j;// 存储最长公共字串的最后一个字符在small中的位置
}
}
else
T[j]=0;
}
}
for(i=0;i<len2;i++){//输出结果
cout<<setw(3)<<T[i]<<" ";
}
cout<<endl;
cout<<"maxle="<<maxlen<<endl;
if(maxlen==0)
cout<<"no common substring"<<endl;
else{
for(i=end_flag-maxlen+1;i<=end_flag;i++)
cout<<small[i];
cout<<endl;
}
}