经典的用动态规划思想解决的问题。首先考虑LIS的最优子结构，设X和Y为两个序列，Z为它们的LIS，其中X={x1，x2，…….，xn},Y={y1,y2,……,ym},Z={z1,z2,……,zk}，思考三种情况：
1：xn==yn，则Z为{x1，，x2，…….，xn}和{y1，y2，……,ym}的LIS，zk==xn==ym；
2：xn！=yn，若zk！=xn，则Z为{x1，x2，…….，xn-1}和{y1，y2，……,ym}的LIS；
3：xn！=yn，若zk！=ym，则Z为{x1，x2，…….，xn}和{y1，y2，……,ym-1}的LIS。
由此可以看出LCS的最优子结构，得出动态方程(f[i][j]代表以xi和yi结尾的最长子序列长度值 )：
f[i][j]=f[i-1][j-1]+1, （xi==yi）；
=min(f[i][j-1], f[i-1][j]) (xi!=yi);
至此，基本可以写出求LIS的代码，而还要构造出最优解的话，要再开设一个数组d[],用d[]记录搜索方向，如图：
代码：
for (i=1;i<=n;i++) for (j=1;j<=m;j++) { if (a[i-1]==b[j-1]) {f[i][j]=f[i-1][j-1]+1; d[i][j]=0; } //a[],b[]存的是字符串 else { f[i][j]=f[i-1][j]; d[i][j]=1; if (f[i][j]<f[i][j-1]) {f[i][j]=f[i][j-1]; d[i][j]=-1; } } }
版权声明：本文为博主原创文章，未经博主允许不得转载。
当你能梦的时候就不要放弃梦
