Javaでの暗記（1D、2D、3D）動的計画法

---

暗記は動的計画法に基づく手法であり、提供された入力の結果を記録することにより、メソッドが同じ入力セットに対して複数回実行されないようにすることで、再帰的アルゴリズムのパフォーマンスを向上させるために使用されます（配列）。再帰的方法のトップダウンアプローチを実装することにより、暗記を実現できます。

基本的なフィボナッチの例を参考にして、このシナリオを理解しましょう

1-D暗記

非定数パラメーターが1つだけ（1つのパラメーターだけが値を変更する）の再帰的アルゴリズムを検討するため、この方法は1次元記憶と呼ばれます。次のコードは、フィボナッチ数列のN番目（Nまでのすべての項）を見つけるためのものです。

例

public int fibonacci(int n) {
   if (n == 0)
      return 0;
   if (n == 1)
      return 1;
   System.out.println("Calculating fibonacci number for: " + n);
   return (fibonacci(n - 1) + fibonacci(n - 2));
}

出力

上記のコードをn=5で実行すると、次の出力が生成されます。

Calculating fibonacci number for: 5
Calculating fibonacci number for: 4
Calculating fibonacci number for: 3
Calculating fibonacci number for: 2
Calculating fibonacci number for: 2
Calculating fibonacci number for: 3
Calculating fibonacci number for: 2

n =5のフィボナッチ値：5

2と3のフィボナッチ数が複数回計算されていることに注意してください。上記の条件のフィボナッチ数列（n =5）の再帰ツリーを描画して、理解を深めましょう。

ここで、ノードの2つの子は、ノードが行う再帰呼び出しを表します。ご覧のとおり、F（3）とF（2）は複数回計算され、各ステップの後に結果をキャッシュすることで回避できます。

結果をキャッシュするためにインスタンス変数のメモ化セットを使用します。最初に、メモ化セットにnがすでに存在するかどうかがチェックされ、存在する場合は値が返され、存在しない場合は値が計算されてセットに追加されます。

例

import java.util.HashMap;
import java.util.Map;
public class TutorialPoint {
   private Map<Integer, Integer> memoizeSet = new HashMap<>(); // O(1)
   public int fibMemoize(int input) {
      if (input == 0)
         return 0;
      if (input == 1)
         return 1;
      if (this.memoizeSet.containsKey(input)) {
         System.out.println("Getting value from computed result for " + input);
         return this.memoizeSet.get(input);
      }
      int result = fibMemoize(input - 1) + fibMemoize(input - 2);
      System.out.println("Putting result in cache for " + input);
      this.memoizeSet.put(input, result);
      return result;
   }
   public int fibonacci(int n) {
      if (n == 0)
         return 0;
      if (n == 1)
         return 1;
      System.out.println("Calculating fibonacci number for: " + n);
      return (fibonacci(n - 1) + fibonacci(n - 2));
   }
   public static void main(String[] args) {
      TutorialPoint tutorialPoint = new TutorialPoint();
      System.out.println("Fibonacci value for n=5: " + tutorialPoint.fibMemoize(5));
   }
}

出力

上記のコードを実行すると、次の出力が生成されます

Adding result in memoizeSet for 2
Adding result in memoizeSet for 3
Getting value from computed result for 2
Adding result in memoizeSet for 4
Getting value from computed result for 3
Adding result in memoizeSet for 5

n =5のフィボナッチ値：5

ご覧のとおり、2と3のフィボナッチ数は再度計算されません。ここでは、入力に対して値が計算され、そうでない場合は特定の入力の値がセットに追加される場合、すべてのフィボナッチ計算がセットでチェックされる前にすでに計算された値を格納するために記憶するHashMapを紹介します。

>

2-D暗記

上記のプログラムには、定数以外のパラメーターが1つしかありませんでした。以下のプログラムでは、再帰呼び出しのたびに値を変更する2つのパラメーターを持つ再帰プログラムの例を取り上げ、2つの非定数パラメーターに記憶を実装して最適化します。これは2D暗記と呼ばれます。

例：-標準の最長共通部分列（LCS）を実装します シーケンスのセットが指定されている場合、最長共通部分列問題は、最大長のすべてのシーケンスの共通部分列を見つけることです。可能な組み合わせは2nです。

例

class TP {
   static int computeMax(int a, int b) {
      return (a > b) ? a : b;
   }
   static int longestComSs(String X, String Y, int m, int n) {
      if (m == 0 || n == 0)
         return 0;
      if (X.charAt(m - 1) == Y.charAt(n - 1))
         return 1 + longestComSs(X, Y, m - 1, n - 1);
      else
         return computeMax(longestComSs(X, Y, m, n - 1), longestComSs(X, Y, m - 1, n));
   }
   public static void main(String[] args) {
      String word_1 = "AGGTAB";
      String word_2 = "GXTXAYB";
      System.out.print("Length of LCS is " + longestComSs(word_1, word_2, word_1.length(),word_2.length()));
   }
}

出力

上記のコードを実行すると、次の出力が生成されます

Length of LCS is 4

上記の中間再帰ツリーでは、lcs（ "AXY"、 "AYZ"）が複数回解決されています。

この問題の重複する部分構造プロパティの結果として、同じ部分問題の事前計算は、記憶または集計を使用することで回避できます。

再帰コードの記憶アプローチは次のように実装されます。

例

import java.io.*;
import java.lang.*;
class testClass {
   final static int maxSize = 1000;
   public static int arr[][] = new int[maxSize][maxSize];
   public static int calculatelcs(String str_1, String str_2, int m, int n) {
      if (m == 0 || n == 0)
         return 0;
      if (arr[m - 1][n - 1] != -1)
         return arr[m - 1][n - 1];
      if (str_1.charAt(m - 1) == str_2.charAt(n - 1)) {
         arr[m - 1][n - 1] = 1 + calculatelcs(str_1, str_2, m - 1, n - 1);
         return arr[m - 1][n - 1];
      }
      else {
         int a = calculatelcs(str_1, str_2, m, n - 1);
         int b = calculatelcs(str_1, str_2, m - 1, n);
         int max = (a > b) ? a : b;
         arr[m - 1][n - 1] = max;
         return arr[m - 1][n - 1];
      }
   }
   public static void main(String[] args) {
      for (int i = 0; i < 1000; i++) {
         for (int j = 0; j < 1000; j++) {
            arr[i][j] = -1;
         }
      }
      String str_1 = "AGGTAB";
      String str_2 = "GXTXAYB";
      System.out.println("Length of LCS is " + calculatelcs(str_1, str_2, str_1.length(),str_2.length()));
   }
}

出力

上記のコードを実行すると、次の出力が生成されます

Length of LCS is 4

アプローチ

メソッド（calculatelcs）には、2つの定数（記憶に影響を与えない）と2つの非定数引数（mおよびn）を持つ4つの引数があることがわかりました。 これは、すべての再帰的なメソッド呼び出しでその値を変更します。したがって、暗記を実現するために、2次元配列を導入してlcs（m、n）の計算値をarr[m-1][n-1]に格納します。 lcs（m、n）の以前の計算がすでに行われているため、同じ引数mとnを持つ関数が再度呼び出されるたびに、これ以上再帰呼び出しを実行せず、arr[m-1][n-1]を返します。 arr [m-1] [n-1]に格納されるため、再帰呼び出しの数が最小限に抑えられます。

3D暗記

これは、3つの非定数引数を持つ再帰プログラムの暗記を実現するためのアプローチです。ここでは、3つの文字列のLCSの長さを計算する例を取り上げています。

ここでのアプローチは、指定された文字列に対して可能なすべてのサブシーケンス（可能なサブシーケンスの合計は3ⁿ）を生成し、それらの中で最も長い共通サブシーケンスと一致させることです。

計算値を格納するための3Dテーブルを導入します。サブシーケンスを検討します。

• A1 [1 ... i] i

• A2 [1 ... j] j

• A3 [1 ... k] k

共通の文字（X [i] ==Y [j] ==Z [k]）が見つかった場合は、残りの文字を繰り返す必要があります。そうでない場合は、次の場合の最大値を計算します

• X[i]を他の人のために繰り返します

• Y[j]を他の人のために繰り返します

• 他の人のためにZ[k]を繰り返します

したがって、上記のアイデアを再帰関数に定式化すると、

f（N、M、K）={1 + f（N-1、M-1、K-1）if（X [N] ==Y [M] ==Z [K] maximum（f（N- 1、M、K）、f（N、M-1、K）、f（N、M、K-1））}

• f（N-1、M、K）=他の人のためにX[i]を繰り返します

• f（N、M-1、K）=他の人のためにY[j]を繰り返します

• f（N、M、K-1）=他の人のためにZ[k]を繰り返します

例

import java.io.IOException;
import java.io.InputStream;
import java.util.*;
class testClass {
   public static int[][][] arr = new int[100][100][100];
   static int calculatelcs(String str_1, String str_2, String str_3, int m, int n, int o) {
         for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
               arr[i][j][0] = 0;
            }
         }
         for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= o; j++) {
               arr[0][i][j] = 0;
            }
         }
         for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= o; j++) {
               arr[i][0][j] = 0;
            }
         }
         for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
               for (int k = 1; k <= o; k++) {
                  if (str_1.charAt(i - 1) == str_2.charAt(j-1) && str_2.charAt(j1) == str_3.charAt(k-1)) {
                     arr[i][j][k] = 1 + arr[i - 1][j - 1][k - 1];
                  }
                  else {
                     arr[i][j][k] = calculateMax(arr[i - 1][j][k], arr[i][j - 1][k], arr[i][j][k - 1]);
                  }
               }
            }
         }
         return arr[m][n][o];
   }
   static int calculateMax(int a, int b, int c) {
      if (a > b && a > c)
         return a;
         if (b > c)
         return b;
         return c;
   }
   public static void main(String[] args) {
      String str_1 = "clued";
      String str_2 = "clueless";
      String str_3 = "xcxclueing";
      int m = str_1.length();
      int n = str_2.length();
      int o = str_3.length();
      System.out.print("Length of LCS is " + calculatelcs(str_1, str_2, str_3, m, n, o));
   }
}

出力

上記のコードを実行すると、次の出力が生成されます

Length of LCS is 4