Memoization (1D, 2D, 3D) Dynamic Programming ใน Java

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับ Memoization เทคนิค Dynamic Programming ที่ใช้เพิ่มประสิทธิภาพ Recursive Algorithm โดยจดจำผลลัพธ์ของ Subproblem ไว้ ไม่ให้คำนวณซ้ำ

หลักการทำงาน

1. ก่อนคำนวณ Subproblem ให้ตรวจสอบว่าคำนวณไปแล้วหรือยัง (Lookup Table)
2. ถ้ามีแล้ว → คืนค่าทันที
3. ถ้ายังไม่มี → คำนวณ เก็บไว้ใน Table แล้วคืนค่า
4. ลด Complexity จาก Exponential เป็น Polynomial

1-D Memoization: Fibonacci

มี Parameter ไม่คงที่ 1 ตัว (n)

แบบ Recursive ธรรมดา (ช้า O(2^n))

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

// n=5: คำนวณ fib(2), fib(3) ซ้ำหลายครั้ง

แบบ Memoization (เร็ว O(n))

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemoization {
    private Map memo = new HashMap<>();

    public int fibMemo(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        if (memo.containsKey(n)) {
            System.out.println("Getting from cache: " + n);
            return memo.get(n);
        }

        int result = fibMemo(n - 1) + fibMemo(n - 2);
        System.out.println("Putting in cache: " + n);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        FibonacciMemoization fm = new FibonacciMemoization();
        System.out.println("Fibonacci(5) = " + fm.fibMemo(5));
    }
}

Output:

Putting in cache: 2
Putting in cache: 3
Getting from cache: 2
Putting in cache: 4
Getting from cache: 3
Putting in cache: 5
Fibonacci(5) = 5

2-D Memoization: Longest Common Subsequence (LCS)

มี Parameter ไม่คงที่ 2 ตัว (m, n) ใช้ 2D Array/Map

Recursive ธรรมดา (ช้า)

public static int lcs(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 + lcs(X, Y, m-1, n-1);
    else
        return Math.max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

Memoization ด้วย 2D Array

public class LCSMemoization {
    static final int MAX = 1000;
    static int[][] dp = new int[MAX][MAX];

    public static int lcsMemo(String X, String Y, int m, int n) {
        if (m == 0 || n == 0) return 0;

        if (dp[m-1][n-1] != -1) return dp[m-1][n-1];

        if (X.charAt(m-1) == Y.charAt(n-1)) {
            dp[m-1][n-1] = 1 + lcsMemo(X, Y, m-1, n-1);
        } else {
            int a = lcsMemo(X, Y, m, n-1);
            int b = lcsMemo(X, Y, m-1, n);
            dp[m-1][n-1] = Math.max(a, b);
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        // Initialize with -1
        for (int i = 0; i < MAX; i++)
            for (int j = 0; j < MAX; j++)
                dp[i][j] = -1;

        String X = "AGGTAB";
        String Y = "GXTXAYB";
        System.out.println("LCS Length: " + lcsMemo(X, Y, X.length(), Y.length()));
    }
}

3-D Memoization: LCS ของ 3 String

มี Parameter ไม่คงที่ 3 ตัว (i, j, k) ใช้ 3D Array

Recurrence Relation

ถ้า X[i] == Y[j] == Z[k]: 1 + f(i-1, j-1, k-1)

มิฉะนั้น: max(f(i-1,j,k), f(i,j-1,k), f(i,j,k-1))

Memoization ด้วย 3D Array

public class LCS3Memoization {
    static int[][][] dp = new int[100][100][100];

    public static int lcs3(String X, String Y, String Z, int m, int n, int o) {
        // Base cases handled by dp initialization (0)

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= o; k++) {
                    if (X.charAt(i-1) == Y.charAt(j-1) && Y.charAt(j-1) == Z.charAt(k-1)) {
                        dp[i][j][k] = 1 + dp[i-1][j-1][k-1];
                    } else {
                        dp[i][j][k] = max3(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]);
                    }
                }
            }
        }
        return dp[m][n][o];
    }

    static int max3(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    public static void main(String[] args) {
        String X = "clued";
        String Y = "clueless";
        String Z = "xcxclueing";

        System.out.println("LCS Length: " + lcs3(X, Y, Z, X.length(), Y.length(), Z.length()));
    }
}

สรุปการเลือกใช้

Memoization vs Tabulation

• Memoization (Top-Down): Recursive + Cache, เขียนง่าย, Stack Overflow ได้ถ้า Deep
• Tabulation (Bottom-Up): Iterative + Table, เร็วกว่าเล็กน้อย, ไม่มี Stack Issue