package algorithm.apps; import utils.com.Matrixer; /** * 最长公共子序列 * 动态规划,记表备查 * @author Toy * */ public class LCS { public void lcs_01(char[] cs,char[] cs2){ int m=cs.length+1; int n=cs2.length+1; int[][] p=new int[m][n]; int[][] q=new int[m][n]; for(int i=0;i<m;i++){ p[i][0]=0; } for(int i=0;i<n;i++){ p[0][i]=0; } Matrixer.show(p, m, n); for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(cs[i-1]==cs2[j-1]){ p[i][j]=p[i-1][j-1]+1; q[i][j]=0; }else if(p[i-1][j]>=p[i][j-1]){ p[i][j]=p[i-1][j]; q[i][j]=1;//up }else{ p[i][j]=p[i][j-1]; q[i][j]=-1;//left } } } Matrixer.show(p, m, n); Matrixer.show(q, m, n); printLCS(cs,q,m-1,n-1); } private void printLCS(char[] cs, int[][] q, int i, int j) { if(i==0||j==0){ return ; } if(q[i][j]==0){ System.out.println(cs[i-1]); printLCS(cs, q, i-1, j-1); }else if(q[i][j]==1){ printLCS(cs,q,i-1,j); }else if(q[i][j]==-1){ printLCS(cs,q,i,j-1); } } /** * @param args */ public static void main(String[] args) { String a="ABCBDABC"; String b="BDCABAC"; LCS c=new LCS(); c.lcs_01(a.toCharArray(), b.toCharArray()); } }