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

动态规划法求解最长公共子序列(含Java代码).doc:..,假设X和Y分别有m和n个元素,则建立一个二维数组C[(m+1)*(n+1)],记录X:与Yj的LCS的长度。将C[i,j]分为三种情况:若i=0或j=0时,C[i,j]=O;若i,j〉O且X[i]=Y[j],C[i,j]=C[i-lj-l]+l;若i,j〉O且X[i]YU],C[i,j]=max{C[i-l,j],C[i,j-l]}。再使川一个m*n的二维数组b,b[i,j]记录C[i,j]的来向:若X[i]=Y[j],则B[i,j]中记入“\”,记此吋b[ij]=l;若X[i]Y[j]且C[i-l,j]〉C[i,j-l],则b[i,j]中记入“T”,记此时B[i,j]=2;若X[i]Y[j]且C[i-l,j]<C[i,j-l],则b[i,j]屮记入记此时B[i,j]=3;若X[i]Y[j]且C[i-1,j]二C[i,j-1],则b[i,j]中记入“f”或“一”,记此时B[i,j]=4;得到了两个数组C口和B[],设计递归输出LCS(X,Y)的算法:LCS_Output(Direction[][],X[],i,j,len,LCS[]){Ifi=0orj=0将LCS[]保存至集合LCSSET中thenreturn;Ifb[i,j]=lthen/*X[i]=Y[j]*/{LCSOutput(b,X,i~l,j-1);将X[i]保存至LCS[len-i];}elseifb[i,j]=2then/*X[i]#Y[j]且C[i_l,j]〉C[i,j-1]*/LCSOutput(b,X,i~l,j)elseifb[i,j]=3then/*X[i]*Y[j]且C[i-1,j]〈C[i,j-1]*/(b,X,i,j-1)elseifb[i,j]=4then/*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),而查找所有的公共子序列的时间复杂度取决于所遍历的路径,而路径是由算法递归的方肉决定的。显然,最好的情况是并且B中的所有值都为1(按斜对角线方向搜索),此时时间复杂度为O(n)。当X和Y序列不存在公共子序列时为算法的最坏情况,因为此时C数组的所有元素都力0,B在每一个节点都要沿着两个不同的方向搜索,即每次都要调用两次LCS_Output,当调用到i=0或>0吋返回,直到搜索完整个数组j结束。该时间复杂度就是计算从点(m,n)到i=0或j=0的所有路径。建立如上图的直角坐标系,设点S(m,n),x轴上的坐标点Pi(l,0)到Pm(m,0),y轴上的系列坐标点Qi(0,l)到Qn(0,n)。因乂^和是搜索路径的边界上的点,点匕不能直接到达点€,点2州也不能直接到达所以点S(m,n)至ijf,P2,…,/%...,和gi,g2,...,g/v..,gn的路径数等价于S(m,n)到点6’(1,1),戸2’(2,1),...,/^(/,1),_6/(所,1)和点21|(1,1),22从^ 又因为点(m,W到(/,力路