动态规划：最长公共子序列

import java.util.Scanner; //最长公共子序列 public class LCS { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); char[] x; char[] y; String stringX=scanner.nextLine(); x=stringX.toCharArray(); String stringY=scanner.nextLine(); y=stringY.toCharArray(); //c[i][j]记录Xi和Yj的最长公共子序列长度 int[][] c=new int[x.length+1][y.length+1]; //b[i][j]记录c[i][j]的值是由哪个子问题解到的 int[][] b=new int[x.length+1][y.length+1]; LCSLength(x, y, x.length, y.length, b,c); System.out.println(c[x.length][y.length]); printLCS(x.length, y.length, x, b); } private static void LCSLength(char[] x,char[]y,int m,int n,int[][] b,int[][]c){ int i,j; for (i = 1; i <= m; i++) { c[i][0]=0; } for (j = 1; j <= n; j++) { c[0][j]=0; } for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { if (x[i-1]==y[j-1]) { c[i][j]=1+c[i-1][j-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; } } } } //打印最长子序列 private static void printLCS(int i,int j,char[] x,int[][] b){ if (i==0||j==0) return; if (b[i][j]==1) { printLCS(i-1, j-1, x, b); System.out.print(x[i-1]); } else if (b[i][j]==2) { printLCS(i-1, j, x, b); } else { printLCS(i, j-1, x, b); } } }