给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。

字符串1：BDCABAD
字符串2：ABCBDA**B

则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA
LCS-最长公共子序列 - 图1

递推实现


LCS-最长公共子序列 - 图2

  1. public class LCS {
  2.     public static void main(String[] args) {
  4.         int[][] dp = new int[m+1][n+1];
  6.         for (int i = 1; i < m+1; i++) {
  7.             for (int j = 1; j < n+1; j++) {
  8.                 if(x.charAt(i-1) == y.charAt(j-1)){
  9.                     dp[i][j] = dp[i-1][j-1] + 1;
  10.                 }else if(dp[i-1][j] >= dp[i][j-1]){
  11.                     dp[i][j] = dp[i-1][j];
  12.                 }else{
  13.                     dp[i][j] = dp[i][j-1];
  14.                 }
  15.             }
  16.         }
  17.         System.out.printf("%s与%s的最长公共子序列为：\n",x,y);
  18.     }
  19. }