最长公共子序列:
LIS是一个典型的用动规解决的问题。
给出两个字符串，求出两串的最长公共子序列的长度。
我们可以构造出他的结构特征。f(i，j)表示str1[1]~str1[i]和str2[1]~str2[j]的最长不下降子序列的长度。
然后他的递归式也随之能推出来，f(i,j)=Max(f(i,j-1),f(i-1,j))(str1[i]!=str2[j])||f(i-1,j-1)(str1[i]==str2[j]);
1 for (int i=1;i<=len1;i++) 2 for (int j=1;j<=len2;j++) 3 if (str1[i]==str2[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); 4 else f[i][j]=max(f[i][j],f[i-1][j]),f[i][j]=max(f[i][j],f[i][j-1]);
原文：http://www.cnblogs.com/SXia/p/6879371.html