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

在本文中，我们将介绍Java中的记忆化动态规划，包括1D、2D和3D的应用。动态规划是一种经典的问题求解方法，通过将问题分解成子问题并保存子问题的解来解决复杂问题。记忆化则是动态规划中常用的优化技术，可以避免重复计算，提高算法效率。

阅读更多：Java 教程

1D记忆化动态规划

1D记忆化动态规划意味着我们使用一维数组来保存子问题的解。这种方法通常适用于线性序列的问题，例如斐波那契数列。

考虑以下问题：求解第n个斐波那契数。斐波那契数列的定义是前两个数是1，之后的每个数都等于前两个数之和。我们可以使用1D记忆化动态规划来解决这个问题。

public class Fibonacci {
    private static long[] memo;

    public static long fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        if (memo[n] != 0) {
            return memo[n];
        }

        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 50;
        memo = new long[n + 1];
        long result = fibonacci(n);
        System.out.println("The " + n + "th Fibonacci number is: " + result);
    }
}

在上面的代码中，我们使用memo数组来保存已经计算过的斐波那契数，避免重复计算。这样，我们就可以大大减少计算量，提高程序效率。

2D记忆化动态规划

2D记忆化动态规划适用于二维网格结构的问题，例如最小路径和、最长公共子序列等。

考虑以下问题：给定一个m x n的网格，每个格子中有一个非负整数，从左上角移动到右下角，每次只能向右或向下移动一步，求最小路径和。我们可以使用2D记忆化动态规划来解决这个问题。

public class MinimumPathSum {
    public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] memo = new int[m][n];

        memo[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            memo[i][0] = memo[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            memo[0][j] = memo[0][j - 1] + grid[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                memo[i][j] = grid[i][j] + Math.min(memo[i - 1][j], memo[i][j - 1]);
            }
        }

        return memo[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        int result = minPathSum(grid);
        System.out.println("The minimum path sum is: " + result);
    }
}

在上面的代码中，我们使用memo二维数组来保存已经计算过的最小路径和。通过填充memo数组，我们可以逐步计算出每个格子的最小路径和，最终得到整个网格的最小路径和。

3D记忆化动态规划

3D记忆化动态规划适用于三维结构的问题。例如，某些问题可能涉及三个参数的变化，例如背包问题、旅行商问题等。

考虑以下问题：有N个物品和一个容量为C的背包，每个物品有重量w和价值v，要求在背包容量不超过C的情况下，选择一些物品放入背包，使得总价值最大。我们可以使用3D记忆化动态规划来解决这个问题。

public class Knapsack {
    public static int knapSack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][][] memo = new int[n + 1][capacity + 1][capacity + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= capacity; j++) {
                for (int k = 0; k <= capacity; k++) {
                    if (i == 0 || j == 0 || k == 0) {
                        memo[i][j][k] = 0;
                    } else if (weights[i - 1] <= j && weights[i - 1] <= k) {
                        memo[i][j][k] = Math.max(values[i - 1] + memo[i - 1][j - weights[i - 1]][k - weights[i - 1]], memo[i - 1][j][k]);
                    } else {
                        memo[i][j][k] = memo[i - 1][j][k];
                    }
                }
            }
        }

        return memo[n][capacity][capacity];
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 8;
        int result = knapSack(weights, values, capacity);
        System.out.println("The maximum value of the knapsack is: " + result);
    }
}

在上面的代码中，我们使用memo三维数组来保存已经计算过的最大价值。通过填充memo数组，我们可以逐步计算出每种背包容量下的最大价值，最终得到总背包容量下的最大价值。

总结

本文介绍了Java中的记忆化动态规划，并示范了1D、2D和3D记忆化的应用。动态规划是一种高效解决问题的方法，记忆化是动态规划中常用的优化技术，可以避免重复计算。在实际问题中，根据问题的特点选择合适的记忆化动态规划方法，能够提高解决问题的效率和准确性。希望本文对你理解Java中的记忆化动态规划有所帮助。