在Java中的记忆化「1D，2D和3D」动态规划

1. 什么是记忆化动态规划

动态规划是一种常用的算法设计和分析技术，其基本思想是将一个复杂问题分解为若干个子问题，通过组合子问题的解来求解原问题。如果直接使用动态规划进行求解，可能会有大量的重复计算，这就是记忆化动态规划的出发点。

记忆化动态规划是一种通过存储子问题的解，并在需要时进行查找的方法，以避免重复计算的动态规划。其核心思想是在实际计算中，对于某一个子问题的解会被反复地使用，而不同的子问题可能会出现重叠，如果我们能够将这些子问题的解进行保存，并在计算时进行查找，就可以避免重复计算，提高算法效率。

2. 记忆化动态规划的应用场景

2.1 一维动态规划

在一维动态规划中，我们通常将已经计算过的子问题的解存储在一个数组中，以便在需要时进行查找。下面是一个简单的例子，描述如何使用一维动态规划来求解斐波那契数列。

int[] cache = new int[1000];
public int fibonacci(int n) {
    if(n == 0 || n == 1) {
        return n;
    }
    if(cache[n] != 0) {
        return cache[n];
    }
    cache[n] = fibonacci(n-1) + fibonacci(n-2);
    return cache[n];
}

在上述代码中，我们定义了一个数组cache来存储已经计算的斐波那契数列的值，如果在计算f(n)的时候，我们发现cache[n]不为0，那么说明f(n)已经计算过了，直接使用cache[n]返回答案即可。

2.2 二维动态规划

在二维动态规划中，我们通常使用一个二维数组来存储已经计算的子问题的解。下面是一个简单的例子，描述如何使用二维动态规划来求解最长公共子序列（LCS）问题。

public int lcs(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int[][] cache = new int[len1+1][len2+1];
    for(int i=1; i<=len1; i++) {
        for(int j=1; j<=len2; j++) {
            if(s1.charAt(i-1) == s2.charAt(j-1)) {
                cache[i][j] = cache[i-1][j-1] + 1;
            } else {
                cache[i][j] = Math.max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[len1][len2];
}

在上述代码中，我们使用一个二维数组cache来存储已经计算的LCS问题的解。cache[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的公共子序列长度。在计算cache[i][j]时，如果s1.charAt(i-1) == s2.charAt(j-1)，那么我们可以将cache[i-1][j-1]加1的结果赋值给cache[i][j]；否则，我们需要比较cache[i-1][j]和cache[i][j-1]的大小，选择较大者赋值给cache[i][j]。

2.3 三维动态规划

在三维动态规划中，我们通常使用一个三维数组来存储已经计算的子问题的解。下面是一个简单的例子，描述如何使用三维动态规划来求解背包问题。

public int knapsack(int[] w, int[] v, int n, int C) {
    int[][][] cache = new int[n+1][C+1][2];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=C; j++) {
            if(j < w[i-1]) {
                cache[i][j][0] = cache[i-1][j][0];
            } else {
                cache[i][j][0] = Math.max(cache[i-1][j][0], cache[i-1][j-w[i-1]][0] + v[i-1]);
            }
            if(cache[i][j][0] == cache[i-1][j][0]) {
                cache[i][j][1] = 0;
            } else {
                cache[i][j][1] = 1;
            }
        }
    }
    int i = n, j = C;
    while(i > 0 && j > 0) {
        if(cache[i][j][1] == 1) {
            System.out.println(i + "th item is included.");
            j -= w[i-1];
        }
        i--;
    }
    return cache[n][C][0];
}

在上述代码中，我们使用一个三维数组cache来存储已经计算的背包问题的解。cache[i][j][0]表示前i个物品，容量为j的背包的最大价值；cache[i][j][1]表示第i个物品是否被包含在背包中。在每次计算完cache[i][j][0]时，会根据两个状态的大小比较，判断第i个物品是否被包含在背包中。

3. 总结

记忆化动态规划是一种常见的算法设计和分析技术，旨在通过存储子问题的解，并在需要时进行查找，以避免重复计算，提高算法效率。在使用记忆化动态规划时，需要考虑问题的规模和复杂度，选择合适的存储方式和查找方式。不同规模和复杂度的问题需要使用不同的动态规划技巧，包括一维、二维和三维动态规划。