eclipse-luna
win732bit and jdk1.7
DELL 显示器
QQ截图工具
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列
方案<1> 枚举法 这种方法是最简单，也是最容易想到的，当然时间复杂度也是龟速的，一个长度为N的字符串，其子序列有2^N个，每个子序列要在第二个长度为N的字符串中去匹配，匹配一次需要O(N)的时间，总共也就是O(N*2^N)，可以看出，时间复杂度为指数级，恐怖的令人窒息。
方案<2> 动态规划: 这里我们采用的是矩阵实现，也就是二维数组。 第一步：先计算最长公共子序列的长度。 第二步：根据长度，然后通过回溯求出最长公共子序列。 注意：动态规划的一个重要性质特点就是解决“子问题重叠”的场景，可以有效的避免重复计算，根据上面的公式其实可以发现C[i,j]一直保存着当前(Xi,Yi)的最大子序列长度。
求解LCS长度辅助表C
功能程序源代码：package ch3.dynamic.algorithm;public class LCS { ////construct thetable of state /*** * * * 这一部分我们使用辅助表，从左上角开始计算每一个位置上LCS的长度 * 判断算法： */ public static int[][] lcsLength(Object[] x,Object[] y){ int m=x.length; int n=y.length; int[][] c = new int[m+1][n+1]; int i,j; for(i=1;i<=m;i++){ c[i][0]=0; } for(j=0;j<=n;j++){ c[0][j]=0; } for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(x[i-1].equals(y[j-1])){ c[i][j]=c[i-1][j-1]+1; }else if(c[i-1][j]>=c[i][j-1]){ c[i][j]=c[i-1][j]; }else{ c[i][j]=c[i][j-1]; } } } return c; } /////print the lcs ////采用递归的方式将结果打印出来 public static void printLcs(int[][] c,Object[] x,Object[] y,int i,int j){ if(i==0||j==0){ return ; } if(x[i-1].equals(y[j-1])){ printLcs(c,x,y,i-1,j-1); System.out.print(x[i-1]+' '); }else if(c[i-1][j]>=c[i][j-1]){ printLcs(c, x, y, i-1, j); }else{ printLcs(c, x, y, i, j-1); } }}
记得关注投票支持我奥
学习这一部分辅助表的构建和使用是一个重要的思想