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

,假设X和Y分别有m和n个元素,则建立一个二维数组C[(m+1)*(n+1)],记录Xi与Yj的LCS的长度。将C[i,j]分为三种情况:若i=0或j=0时,C[i,j]=0;若i,j>0且X[i]=Y[j],C[i,j]=C[i-1,j-1]+1;若i,j>0且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],则B[i,j]中记入“↖”,记此时b[i,j]=1;若X[i]
Y[j]且C[i-1,j]>C[i,j-1],则b[i,j]中记入“↑”,记此时B[i,j]=2;若X[i]
Y[j]且C[i-1,j]<C[i,j-1],则b[i,j]中记入“←”,记此时B[i,j]=3;若X[i]
Y[j]且C[i-1,j]=C[i,j-1],则b[i,j]中记入“↑”或“←”,记此时B[i,j]=4;得到了两个数组C[]和B[],设计递归输出LCS(X,Y)的算法:LCS_Output(Direction[][],X[],i,j,len,LCS[]){Ifi=0orj=0将LCS[]保存至集合LCS_SET中thenreturn;Ifb[i,j]=1then/*X[i]=Y[j]*/{LCS_Output(b,X,i-1,j-1);将X[i]保存至LCS[len-i];}elseifb[i,j]=2then/*X[i]¹Y[j]且C[i-1,j]>C[i,j-1]*/LCS_Output(b,X,i-1,j)elseifb[i,j]=3then/*X[i]¹Y[j]且C[i-1,j]<C[i,j-1]*/LCS_Output(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),而查找所有的公共子序列的时间复杂度取决于所遍历的路径,而路径是由算法递归的方向决定的。显然,最好的情况是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)。因为是搜索路径的边界上的点,点不能直接到达点,点也不能直接到达,所以点到和的路径数等价于到点和点的路径数,又因为点到路径数为,设总路径数为,则有程序流程图如下所示程序源码packageHomework2;;;;im