首页 > 代码库 > 经典算法之动态规划--求最大公共子序列
经典算法之动态规划--求最大公共子序列
作为新人，之前对C,C++了解的比较少，关于算法方面更是一窍不通，但最近却痴迷上了算法，哪怕是前辈们不屑一顾的东东，我弄明白了后都会欣喜若狂！
今天将遇到的问题和java实现贴出来和同为新人的博友分享，老鸟可以可以直接关网页了。
定义：
子序列：一个给定序列的子序列是再该序列中删去若干元素后得到的序列。即：给定{x1,x2,...,xm}和Z={z1,z2,...,zk}，X的子序列是指存在一个严格递增下表序列{i1,i2,...ik}
使得对所有的j=1,2,...k,都有zj=xij。例如：Z={b,d,c,a}是X={a,b,c,d,c,b,a}的一个子序列
公共子序列：如果Z是序列X的子序列，又是序列Y的子序列，则称Z是序列X和序列Y的公共子序列。例如：序列“bcba” 是"abcbdab"和“bdcaba”的公共子序列
问题：
给定两个序列X={x1,x2,...xm}和Y={y1,y2,...,yn}，找出序列X,Y的最长公共子序列。
思路： f(i,j)表示第一个序列的第i元素后的最大子序列及第二个序列的第j元素后的最大子序列的公共子序列长度
如果i=1,j=1,且有x1=y1,那么f(1,1)=f(2,2)+1;
同理：xi == xj , 那么f(i,j)=f(i+1,j+1)+1;
如果 xi != xj , 那么f(i,j)=Max(f(i,j+1) , f(i+1,j));
这样，当i=x.length 或 j=y.length 时，越界，值为0；
我们已经找到了最优值了，如何获取这个最优解呢？
我们可以用个二维数组boolean [][]s 来记录在寻找最优值时xi和yj的比较结果，相等true, 否则false；
如果i=0,j=0, s[0][0]=true,且f(i,j)=f(0,0),那么x[0]就是最优解的第一个元素，
同理，如果s[i][j]=true,且f(i,j)=f(0,0)-w , (其中w 从0开始，每确定公共序列中的一项时，w+1)；
over！
java代码如下：
//动态规划//求最大公共子序列public class Demo7 { public static void main(String[]args){ String a ="abcdefghi"; String b ="efghiabcd"; GetBest(a.toCharArray(),b.toCharArray(),a.length(),b.length()); } public static void GetBest(char[]x,char[]y,int m,int n){ boolean[][] s=new boolean[x.length][y.length]; getMax(x,y,0,0,s); for(int t=0,w=0,i=0;i<m;i++){ for(int j=t;j<n;j++){ if(s[i][j]==true&&getMax(x,y,i,j,s)==getMax(x,y,0,0,s)-w){ System.out.print(x[i]+" "); w++; t=j+1; break; } } } } public static int getMax(char[]x,char[]y,int m,int n,boolean[][] s){ if(m==x.length||n==y.length){ return 0; } if(x[m]==y[n]){ s[m][n]=true; return getMax(x,y,m+1,n+1,s)+1; }else{ s[m][n]=false; if(getMax(x,y,m,n+1,s)>getMax(x,y,m+1,n,s)){ return getMax(x,y,m,n+1,s); }else{ return getMax(x,y,m+1,n,s); } } }}