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

《动态规划法求解最长公共子序列(含java代码)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、公共子序列问题徐康123183一.算法设计假设有两个序列X和Y，假设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]=

2、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]

3、中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]*/LCS.Output(b,X,i,j-1)elseifb[i,j]=4then/*X[i]#Y[j]且C[i-1,j]=C[i,j-

4、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或

5、＞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

6、（1，1），22从^

7、又因为点（m，W到（/，力路径数为设总路径数为n则有7=1，卜2n+m-3«+w-lmn-¥m+...+C：（C；r：_24-C:_34-...+C：+CL）三.程序流程图如下所示ApackageHomework2;importjava.io-BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.HashSet;importjava.util.Set;publicclassLCS{intC[][];//使用

8、集合去重//返回公共子序列长度intB[][];SetLCSSET=newHashSet();publicintLCSLength(charX[]，charY[]){intm=X.length;intn=Y.length;C=newint[X.length][Y.length];B=newint[X.length][Y.length];for(inti=0;i

9、ntj=1;jC[i]U-l]){c[i]U]=c[i-i]U]；B[i]U]=2;}elseif(C[i-l]

10、j]