Java动态规划求最长公共子序列(LCS)
最长公共子序列(LCS)
定义:在序列X和序列Y中同时出现的元素,按照脚标从小到大排列的这样的序列。
String x = "ABCBDABGGGTT";
String y = "BDCABATGGGTT";
x,y的最长公共子序列为BCBAGGGTT;
package shu_quan.dynamic;
import java.util.ArrayList;
/**
*
* @author quan
*777代表两个x,y序列长度相同且最长公共子序列是Xn和Yn的情况,存在相同的元素
*444代表x,y两个序列长度不同且最长公共子序列是x和Yn-1的情况,
*666代表x,y两个序列长度不同且最长公共子序列是Xn-1和Yn的情况,
*/
public class LongestCommonSubsequence {
public static void main(String[] args) {
//初始化两个字符序列
String x1 = "ABCBDABGGGTT";
String x2 = "BDCABATGGGTT";
char[] x = x1.toCharArray();
char[] y = x2.toCharArray();
ArrayList<int[][]> ls = new ArrayList<>();
ArrayList<int[][]> ls1 = longestCommonSubsequence(x,y,ls);
int[][] b = ls.get(0);
int[][] c = ls.get(1);
//打印c矩阵
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < c[0].length; j++) {
System.out.print(c[i][j]+" ");
}
System.out.println();
}
System.out.println("===================================================================");
//打印b矩阵
for (int i = 0; i < b.length; i++) {
for (int j = 0; j < b[0].length; j++) {
System.out.print(b[i][j]+" ");
}
System.out.println();
}
//构造LCS
StringBuilder sb = new StringBuilder();
printLongestCommonSubsequence(sb,b,x,x.length,y.length);
System.out.println(sb.toString());
}
/**
重构最优解LCS
*/
private static void printLongestCommonSubsequence(StringBuilder sb, int[][] b, char[] x, int i, int j) {
if(i==0 || j==0)
return;
//777代表两个x,y序列长度相同且最长公共子序列是Xn和Yn的情况,存在相同的元素
if(b[i][j] == 777) {
printLongestCommonSubsequence(sb,b,x,i-1,j-1);
sb.append(x[i-1]);
//444代表x,y两个序列长度不同且最长公共子序列是x和Yn-1的情况
}else if(b[i][j] == 444) {
printLongestCommonSubsequence(sb,b,x,i,j-1);
//666代表x,y两个序列长度不同且最长公共子序列是Xn-1和Yn的情况
}else{
printLongestCommonSubsequence(sb,b,x,i-1,j);
}
}
/**
把c矩阵和b矩阵放入容器中返回容器。
*/
private static ArrayList<int[][]> longestCommonSubsequence(char[] x, char[] y, ArrayList<int[][]> ls) {
int m = x.length;
int n = y.length;
int[][] c = new int[m+1][n+1];
int[][] b = new int[m+1][n+1];
//c[i][j]表示xi和yi的LCS的长度,当i或者j等于0,序列的长度也为0.
for (int i = 0; i < c.length; i++) {
c[i][0] = 0;
}
for (int i = 0; i < c[0].length; i++) {
c[0][i] = 0;
}
for(int i=1; i <= m; i++) {
for(int j=1; j <=n; j++) {
if(x[i-1] == y[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 777;
}else if(c[i-1][j]>=c[i][j-1]){
c[i][j] = c[i-1][j];
b[i][j] = 666;
}else {
c[i][j] = c[i][j-1];
b[i][j] = 444;
}
}
}
ls.add(b);
ls.add(c);
return ls;
}
}
运行结果:
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 2 2 2 2 2 2 2 2
0 1 1 2 2 2 2 2 2 2 2 2 2
0 1 1 2 2 3 3 3 3 3 3 3 3
0 1 2 2 2 3 3 3 3 3 3 3 3
0 1 2 2 3 3 4 4 4 4 4 4 4
0 1 2 2 3 4 4 4 4 4 4 4 4
0 1 2 2 3 4 4 4 5 5 5 5 5
0 1 2 2 3 4 4 4 5 6 6 6 6
0 1 2 2 3 4 4 4 5 6 7 7 7
0 1 2 2 3 4 4 5 5 6 7 8 8
0 1 2 2 3 4 4 5 5 6 7 8 9
===================================================================
0 0 0 0 0 0 0 0 0 0 0 0 0
0 666 666 666 777 444 777 444 444 444 444 444 444
0 777 444 444 666 777 444 444 444 444 444 444 444
0 666 666 777 444 666 666 666 666 666 666 666 666
0 777 666 666 666 777 444 444 444 444 444 444 444
0 666 777 666 666 666 666 666 666 666 666 666 666
0 666 666 666 777 666 777 444 444 444 444 444 444
0 777 666 666 666 777 666 666 666 666 666 666 666
0 666 666 666 666 666 666 666 777 777 777 444 444
0 666 666 666 666 666 666 666 777 777 777 444 444
0 666 666 666 666 666 666 666 777 777 777 444 444
0 666 666 666 666 666 666 777 666 666 666 777 777
0 666 666 666 666 666 666 777 666 666 666 777 777
BCBAGGGTT
C[i][j]的值为序列Xi和Yj的最长公共子序列的值。
矩阵b比较抽象:构造LCS。
以下图(来自算法导论)说明数字777,444,666的含义,代表了计算c的选择指向↖、←、↑ ,b[i][j]的指向对应计算c[i][j]时所选的子问题最优解,按照箭头的方向就能够追踪得到任意c[i][j]最长公共子序列。使用递归的方式求LCS。