Javaでの最小共通部分列（LCS）の実装方法

1. 動的計画法（Dynamic Programming）を使用する方法: 動的計画法は、部分問題の結果を利用して最適解を求める手法です。以下は、動的計画法を使用してLCSを求めるJavaのコード例です。

   public static String findLCS(String s1, String s2) {
      int m = s1.length();
      int n = s2.length();
      int[][] dp = new int[m + 1][n + 1];
      for (int i = 0; i <= m; i++) {
          for (int j = 0; j <= n; j++) {
              if (i == 0 || j == 0)
                  dp[i][j] = 0;
              else if (s1.charAt(i - 1) == s2.charAt(j - 1))
                  dp[i][j] = dp[i - 1][j - 1] + 1;
              else
                  dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
          }
      }
      StringBuilder lcs = new StringBuilder();
      int i = m, j = n;
      while (i > 0 && j > 0) {
          if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
              lcs.insert(0, s1.charAt(i - 1));
              i--;
              j--;
          } else if (dp[i - 1][j] > dp[i][j - 1]) {
              i--;
          } else {
              j--;
          }
      }
      return lcs.toString();
   }

2. 再帰を使用する方法: 再帰を使用してLCSを求めることもできます。以下は、再帰を使用してLCSを求めるJavaのコード例です。

   public static String findLCS(String s1, String s2) {
      if (s1.isEmpty() || s2.isEmpty())
          return "";
      char x = s1.charAt(0);
      char y = s2.charAt(0);
      String remaining1 = s1.substring(1);
      String remaining2 = s2.substring(1);
      if (x == y)
          return x + findLCS(remaining1, remaining2);
      else {
          String lcs1 = findLCS(s1, remaining2);
          String lcs2 = findLCS(remaining1, s2);
          return (lcs1.length() > lcs2.length()) ? lcs1 : lcs2;
      }
   }

これらはLCSを求めるための基本的な方法です。他にもさまざまなアプローチや最適化手法がありますが、上記のコード例は初学者にも理解しやすく、実用的です。また、長さだけでなく実際のLCS自体を求める方法も提供しています。