动态规划-最长的公共子序列（超详解java）
动态规划-最长的公共子序列（java）
先说一下什么是公共子序列： 例如对于字符串"ABCDEF"，ABCD是其一个子序列，ABEF也是一个子序列。子序列不要求连续性,与公共子字符串区分一下，而且最长公共子序列不一定是唯一的。
问题分析：
给定两个子序列X={x1,x2,x3…,xm}和Y={y1,y2,y3…yn},找出X和Y的一个最长的公共子序列。 例如：X={A,B,C,B,A,D,B}，Y={B,C,B,A,A,C},那么最长公共子序列是B,C,B,A。 如何找到最长公共子序列呢？ 能不能用动态规划来解决该问题呢？ 下面分析该问题是否具有最优子结构性质。 （1）分析最优解的结构特征 假设已经知道Zk={z1,z2，z3…,zk}是Xm={x1,x2,x3，…xm}和Yn={y1,y2,y3,…yn}的最长公共子序列。这个假设很重要，我们都是这样假设已经知道最优解。 那么可以分三种情况讨论。 ①. xm=yn=zk；那么Zk-1={z1,z2，z3…,zk-1}是Xm-1和Yn-1的最长公共子序列，应该容易理解吧。 ②. xm≠yn, xm≠zk；我们可以把xm去掉，那么Zk是Xm-1和Yn的最长公共子序列。 ③. yn≠xm, yn≠zk; 我们可以把yn去掉，那么Zk是Xm和Yn-1的最长公共子序列。 （2）建立最优值的递归式 设c[i][j]表示Xi和Yj的最长公共子序列长度。 ①. xm=yn=zk；那么c[i][j]=c[i-1][j-1]+1; ②. xm≠yn, xm≠zk；那么我们只需要求解Xi和Yj-1的最长公共子序列和Xi-1和Yj的最长公共子序列，比较它们的长度那个更大，就取哪一个值。即c[i][j]=max{c[i][j-1],c[i-1][j]}. ③. 最长公共子序列长度递归表达式：
算法设计
填表就跟着程序走一遍，也方便理解，这里就不填了
