Javaで学ぶメモ化（1次元・2次元・3次元）動的計画法の基礎と実装

メモ化（Memoization）は動的計画法に基づく技法の一つで、同じ入力に対して同じ計算を二度以上実行しないようにすることで、再帰アルゴリズムの性能を向上させるためのものです。具体的には、引数ごとの計算結果を配列などのキャッシュに記録しておき、同じ入力で再度呼び出された際には保存済みの結果を即座に返します。メモ化は、再帰メソッドをトップダウン方式で実装することで実現できます。

ここでは、基本的なフィボナッチ数列の例を通じて、この仕組みを順を追って理解していきましょう。

1次元（1-D）メモ化

値が変化する非定数のパラメータが1つだけの再帰アルゴリズムにメモ化を適用する場合、これを1次元（1-D）メモ化と呼びます。以下のコードは、フィボナッチ数列の第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

注目すべきは、n=2とn=3のフィボナッチ数が複数回計算されている点です。n=5の場合の再帰木を描いてみると、この状況がより明確に理解できます。

再帰木では、各ノードの子がそのノードが行う再帰呼び出しを表しています。見てのとおり F(3) と F(2) が何度も計算されており、これは各ステップの結果をキャッシュすることで回避可能です。

そこで、結果をキャッシュするためのインスタンス変数 memoizeSet（HashMap）を用意します。まず n がすでに memoizeSet に存在するかどうかを確認し、存在すればその値を返し、存在しなければ値を計算してセットに追加します。

例（メモ化版）

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

このように、n=2とn=3のフィボナッチ数は再計算されていません。HashMapによるメモ化を導入したことで、フィボナッチ計算の前に毎回キャッシュを確認し、計算済みの入力であればその値を使用し、未計算であれば新たに結果をセットへ格納する仕組みになっています。素朴な再帰では指数時間 O(2ⁿ) かかるところが、メモ化により線形時間 O(n) まで大幅に改善されます。

2次元（2-D）メモ化

先ほどのプログラムでは非定数パラメータは1つでした。次のプログラムでは、再帰呼び出しごとに値が変化する2つの引数を持つ再帰プログラムを例に、両方の非定数引数に対してメモ化を実装して最適化を行います。これを2次元（2-D）メモ化と呼びます。

例として、標準的な最長共通部分列（LCS：Longest Common Subsequence）問題を実装します。複数の文字列が与えられたとき、すべての文字列に共通する部分列のうち最大の長さを持つものを見つける問題です。考えられる組み合わせは2ⁿ通りあります。

例（素朴な再帰）

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") といった同一の部分問題が複数回解かれていることが分かります。

この問題は「部分問題の重複」という性質を持つため、メモ化や表形式（Tabulation）を用いることで、同じ部分問題の再計算を避けられます。

再帰コードにメモ化を適用した実装は次のとおりです。

例（メモ化版）

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メソッドには4つの引数があり、そのうち2つは定数（メモ化には影響しません）、残る2つの非定数引数(m と n)が再帰呼び出しごとに変化します。メモ化を実現するために、計算済みの lcs(m,n) の値を arr[m-1][n-1] に格納する2次元配列を導入します。同じ m と n を引数に関数が再度呼び出されたときには追加の再帰呼び出しを行わず、以前の計算結果が保存された arr[m-1][n-1] の値をそのまま返します。これにより、再帰呼び出しの総回数を最小限に抑えられます。

3次元（3-D）メモ化

これは、非定数の引数を3つ持つ再帰プログラムに対してメモ化を実現する手法です。ここでは、3つの文字列に対するLCSの長さを求める例を取り上げます。

アプローチとしては、与えられた文字列から考えられるすべての部分列（合計3ⁿ通り）を生成し、その中から最長の共通部分列を探索します。

計算済みの値を格納するために、3次元のテーブルを導入します。部分列は以下のように考えます。

• A1[1...i]、i < N
• A2[1...j]、j < M
• A3[1...k]、k < K

共通の文字が見つかった場合（X[i]==Y[j]==Z[k]）は、残りの部分について再帰的に処理を続けます。そうでない場合は、次の3つのケースの最大値を計算します。

• X[i] を除外し、残りを再帰的に処理する
• Y[j] を除外し、残りを再帰的に処理する
• Z[k] を除外し、残りを再帰的に処理する

このアイデアを再帰関数として定式化すると、次のようになります。

f(N,M,K) = { 1 + f(N-1,M-1,K-1)　（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(j - 1) == 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

まとめ

メモ化は、重複する部分問題の計算結果をキャッシュすることで再帰アルゴリズムを高速化する強力な手法です。変化する引数の数に応じて1次元・2次元・3次元のキャッシュ構造を選択することで、フィボナッチ数列のような単純な問題から、LCSのような組み合わせ爆発を起こしやすい問題まで、幅広い課題を効率的に解決できます。再帰的なトップダウンの設計思想を保ちながら計算量を大幅に削減できるのが、メモ化の大きな魅力といえるでしょう。