动态规划法求解最长公共子序列(含Java代码).doc

公共子序列问题 徐康123183 一．算法设计 假设有两个序列X和Y，假设X和Y分别有m和n个元素，则建立一个二维数组C[(m+1)*(n+1)]，记录Xi与Yj的LCS的长度。将C[i,j]分为三种情况： 若i =0 或j =0时，C[i,j]=0； 若i,j0且X[i]=Y[j]，C[i,j]=C[i-1,j-1]+1； 若i,j0且X[i](Y[j],C[i,j]=max{C[i-1,j],C[i,j-1]}。 再使用一个m*n的二维数组b，b[i,j]记录C[i,j]的来向: 若X[i]=Y[j]，则[i,j]中记入“↖”b[i,j] = 1；若X[i](Y[j]C[i-1,j] C[i,j-1]，则b[i,j]中记入“↑”[i,j] = 2； 若X[i](Y[j]C[i-1,j] C[i,j-1]，则b[i,j]中记入“←”[i,j] = 3； LCS_Output(Direction[][], X[], i, j, len,LCS[]){ If i=0 or j=0 将LCS[]保存至集合LCS_SET中 then return; If b[i,j]=1 then /*X[i]=Y[j]*/ {LCS_Output(b,X,i-1,j-1)； 将X[i]保存至LCS[len-i]；} else if b[i,j]=2 then /*X[i](Y[j]且C[i-1,j]C[i,j-1]*/ LCS_Output(b,X,i-1,j) else if b[i,j]=3 then /*X[i](Y[j]且C[i-1,j]C[i,j-1]*/ LCS_Output(b,X,i,j-1) else if b[i,j]=4 then /*X[i](Y[j]且C[i-1,j]=C[i,j-1]*/ LCS_Output(b,X,i-1,j) LCS_Output(b,X,i,j-1) } 算法时间复杂度分析 由上述对算法的分析得知，求辅助数组C和B所消耗的时间复杂度为O（mn），而查找所有的公共子序列的时间复杂度取决于所遍历的路径，而路径是由算法递归的方向决定的。显然，最好的情况是m=n并且B中的所有值都为1（按斜对角线方向有哪些信誉好的足球投注网站），此时时间复杂度为O（n）。当X和Y序列不存在公共子序列时为算法的最坏情况，因为此时C数组的所有元素都为0，B在每一个节点都要沿着两个不同的方向有哪些信誉好的足球投注网站，即每次都要调用两次LCS_Output,当调用到i=0或j=0时返回，直到有哪些信誉好的足球投注网站完整个m*n数组才结束。 该时间复杂度就是计算从点（m,n）到i=0或j=0的所有路径。建立如上图的直角坐标系，设点S（m，n）,轴上的坐标点P1(1,0) 到Pm(m,0)，轴上的系列坐标点Q1(0,1) 到Qn(0,n)。 因为是有哪些信誉好的足球投注网站路径的边界上的点，点不能直接到达点，点也不能直接到达，所以点到和的路径数等价于到点和点的路径数，又因为点到路径数为，设总路径数为，则有 程序流程图如下所示 程序源码 package Homework2; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; public class LCS { int C[][]; int B[][]; Set LCS_SET = new HashSet(); //使用集合去重 public int LCSLength(char X[], char Y[]) { //返回公共子序列长度 int m = X.length; int n = Y.length; C = new