枚举算法
的时间复杂度为指数级时间复杂度。
注意: 可能同时有多个长度相等的最长公共子序列!
倒推—从最后一个元素开始分析
输入序列对(X(m-1),Y(n-1) ),(X(m-1),Yn ) 和(Xm,Y(n-1) )都分别表示一个子问题 (xm等于或不等于yn,都可以分解为这三个子问题)
子问题可以通过两个参数确定,即序列 X 的长度和序列 Y 的长度
C(i,j)表示序列Xi={x1,x2,…,xi }和Yj={y1,y2,…,yj } 的最长公共子序列长度
C(m, n)则表示原问题的最长公共子序列长度
两种情况
:
注意:
当第一次遍历 自底向上求解时,X[1] != Y[1],所以走第三条路:求c[0][1] c[1][0]的最大值,但是这两个值都是0,所以取哪一个都可以,所以后续求最长公共子序列的 序列时,这里的左箭头和上箭头都是一样的,
代码的输出 就是最长公共子序列的长度
public class Main {public static int MAX = 1000;public static int lcsLength(char[] strX,char[] strY) {int[][] C = new int[MAX][MAX], B = new int[MAX][MAX];int i, j;int m = strX.length + 1;int n = strY.length + 1;for (i = 0; i < m; i++)C[i][0] = 0; //初始化第一行for (j = 0; j < n; j++)C[0][j] = 0; //初始化第一列for (i = 1; i < m; i++) {for (j = 1; j < n; j++) {if (strX[i-1] == strY[j-1]) {C[i][j] = C[i-1][j-1] + 1;B[i][j] = 1;} else if(C[i - 1][j] >= C[i][j - 1]) {C[i][j] = C[i-1][j];B[i][j] = 2;} else {C[i][j] = C[i][j-1];B[i][j] = 3;}}// end for(j}//end for(ireturn C[m - 1][n - 1];}public static void main(String[] args) {char[] x = {'A', 'B', 'C', 'B', 'D', 'A', 'B'};char[] y = {'B', 'D', 'C', 'A', 'B', 'A'};int i = lcsLength(x, y);System.out.println(i);}
}
下一篇:双亲委派模型机制