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

1、 公共子序列问题 徐康一算法设计 假设有两个序列X和Y，假设X和Y分别有m和n个元素，则建立一个二维数组C(m+1)*(n+1)，记录Xi与Yj的LCS的长度。将Ci,j分为三种情况： 若i =0 或j =0时，Ci,j=0； 若i,j0且Xi=Yj，Ci,j=Ci-1,j-1+1； 若i,j0且XiYj,Ci,j=maxCi-1,j,Ci,j-1。 再使用一个m*n的二维数组b，bi,j记录Ci,j的来向: 若Xi=Yj，则Bi,j中记入“”，记此时bi,j = 1； 若XiYj且Ci-1,j Ci,j-1，则bi,j中记入“”，记此时Bi,j = 2； 若XiYj且Ci-1,j Ci,j-

2、1*/ LCS_Output(b,X,i-1,j) else if bi,j=3 then /*XiYj且Ci-1,jCi,j-1*/ LCS_Output(b,X,i,j-1) else if bi,j=4 then /*XiYj且Ci-1,j=Ci,j-1*/ LCS_Output(b,X,i-1,j) LCS_Output(b,X,i,j-1) 2 算法时间复杂度分析 由上述对算法的分析得知，求辅助数组C和B所消耗的时间复杂度为O（mn），而查找所有的公共子序列的时间复杂度取决于所遍历的路径，而路径是由算法递归的方向决定的。显然，最好的情况是m=n并且B中的所有值都为1（按斜对角线方向搜

3、索），此时时间复杂度为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)。因为是搜索路径的边界上的点，点不能直接到达点，点也不能直接到达，所以点到和的路径数等价于到点和点的路径数，又因为点到路径数为，设总路径数为，则有

4、3 程序流程图如下所示4 程序源码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;

5、int n = Y.length;C = new intX.lengthY.length;B = new intX.lengthY.length;for (int i = 0; i m; i+) Ci0 = 0;Bi0 = 0;for (int j = 0; j n; j+) C0j = 0;B0j = 0;for (int i = 1; i m; i+) for (int j = 1; j Cij - 1) Cij = Ci - 1j;Bij = 2; else if (Ci - 1j Cij - 1) Cij = Cij - 1;Bij = 3; else Cij = Ci - 1j;Bi

6、j = 4;return Cm - 1n - 1;public void LCS_Output(int Direction, char X, int i, int j, int len,char LCS) int lcslen = len;if (i = 0 | j = 0) LCS_SET.add(String.valueOf(LCS);return;if (Bij = 1) LCSlen - 1 = Xi;len-;LCS_Output(B, X, i - 1, j - 1, len, LCS); else if (Bij = 2) LCS_Output(B, X, i - 1, j, l

7、en, LCS); else if (Bij = 3) LCS_Output(B, X, i, j - 1, len, LCS); else if (Bij = 4) LCS_Output(B, X, i - 1, j, len, LCS);LCS_Output(B, X, i, j - 1, len, LCS);/* * param args */public static void main(String args) throws IOException / TODO Auto-generated method stubchar X, Y;BufferedReader buf = null

8、;buf = new BufferedReader(new InputStreamReader(System.in);System.out.println(请输入一个序列);X = buf.readLine().toCharArray();char X_temp = new charX.length + 1;for (int i = 0; i X.length; i+) X_temp0 = ;X_tempi + 1 = Xi;System.out.println(请输入一个序列);Y = buf.readLine().toCharArray();char Y_temp = new charY.

9、length + 1;for (int i = 0; i Y.length; i+) Y_temp0 = ;Y_tempi + 1 = Yi;System.out.print(X=);for (char x : X) System.out.print(x);System.out.println();System.out.print(Y=);for (char y : Y) System.out.print(y);System.out.println();LCS lcs = new LCS();int len = lcs.LCSLength(X_temp, Y_temp);char LCS = new charlen;int m = X.length;int n = Y.length;System.out.println(最长公共子序列长度为: + len); / 输出最长子序列长度System.out.print(最长公共子序列有：);lcs