```java package net.zhaoxuyang.common.algorithm.dp; /** * 最長公共子序列 * * @author zhaoxuyang */ public class LastestCommonSequence { public static void main(String[] args) { String x = "ABCBDAB"; String y = "BDCABA"; int m = x.length(); int n = y.length(); int[][] c = new int[m + 1][n + 1]; int[][] b = new int[m + 1][n + 1]; lscLength(x.toCharArray(), y.toCharArray(), c, b); // for (int i = 0; i <= x.length(); i++) { // for (int j = 0; j <= y.length(); j++) { // System.out.print(b[i][j]+" "); // } // System.out.println(); // } lcs(x.length(), y.length(), x.toCharArray(), b); } /** * <pre> * ------------------------------------------------------------ * = 0 i=0 || j=0 * c[i][j] = c[i-1][j-1]+1 i,j>0 && x[i]=y[j] * = max(c[i][j-1],c[i-1][j]) i,j>0 && x[i]!=y[j] * * b[i][j]=1 表示c[i][j]由c[i-1][j-1]+1 得到 * b[i][j]=2 表示c[i][j]由c[i][j-1] 得到 * b[i][j]=3 表示c[i][j]由c[i-1][j] 得到 * ------------------------------------------------------------ * i行j列，初始時c[i][0]=0,c[0][j]=0 * B D C A B A * 0 0 0 0 0 0 0 * A 0 * B 0 * C 0 * B 0 * D 0 * A 0 * B 0 * ------------------------------------------------------------ * </pre> * * @param x X序列 * @param y Y序列 * @param c 存入最優值 * @param b 存入最優值的來源 */ private static void lscLength(char[] x, char[] y, int[][] c, int[][] b) { for (int i = 1; i <= x.length; i++) { for (int j = 1; j <= y.length; j++) { if (x[i - 1] == y[j - 1]) { c[i][j] = c[i - 1][j - 1] + 1; b[i][j] = 1; } else if (c[i][j - 1] > c[i - 1][j]) { c[i][j] = c[i][j - 1]; b[i][j] = 2; } else { c[i][j] = c[i - 1][j]; b[i][j] = 3; } } } } /** * 根據記錄下的信息構造最優解 */ private static void lcs(int i, int j, char[] x, int[][] b) { if (i == 0 || j == 0) { return; } switch (b[i][j]) { case 1: lcs(i - 1, j - 1, x, b); visit(x[i - 1]); break; case 2: lcs(i, j - 1, x, b); break; default: lcs(i - 1, j, x, b); break; } } /** * 如何處理最優解，例如打印，或者添加到StringBuilder中 * @param c */ private static void visit(char c) { System.out.print(c); } } ```