最長公共子序列-Java

最長公共子序列Java實作

• 動态規劃
• 講解視訊 bilibili上最好的講解
• 代碼：

  package classic;
  
  public class LongestCommonSubsequence {
      public int solve(String a, String b) {
          //
          int[][] ans = new int[b.length() + 1][a.length() + 1];
  //        初始化
          for (int i = 0; i <= a.length(); i++)
              ans[0][i] = 0;
          for (int j = 0; j <= b.length(); j++)
              ans[j][0] = 0;
          int x, y;
          for (int i = 0; i < a.length(); i++) {
              for (int j = 0; j < b.length(); j++) {
                  x = i + 1;
                  y = j + 1;
                  if (a.charAt(i) == b.charAt(j))
                      ans[y][x] = ans[y - 1][x - 1] + 1;
                  else
                      ans[y][x] = Math.max(ans[y - 1][x], ans[y][x - 1]);
              }
          }
          return ans[b.length()][a.length()];
      }
  
      public static void main(String[] args) {
          LongestCommonSubsequence longestCommonSubsequence = new LongestCommonSubsequence();
  //        測試資料
          String a = "abc";
          String b = "cba";
          String c = "";
          String d = "ac";
          System.out.println(longestCommonSubsequence.solve("aggtab", "gxtxayb"));
          System.out.println("a c："+longestCommonSubsequence.solve(a,c));
          System.out.println("a d："+longestCommonSubsequence.solve(a,d));
          System.out.println("b d："+longestCommonSubsequence.solve(b,d));
          System.out.println("a a："+longestCommonSubsequence.solve(a,a));
      }
  }
  
             

• 示意圖