硬币找零问题动态规划解决方案的思路

Question

我正在学习动态编程，并遇到了这个著名的coins change problem。

解决该问题的递归关系由]给出>

countCoinsChangeRec(arr, sum - arr[i], i) + countCoinsChangeRec(arr, sum, i - 1);

最简单的优化问题的方法是存储子问题的解。因此，我为Map的每个值都维持了(sum,i)。通过不再解决相同的问题。

        String key = sum + ":" + i;    
        Integer memoizedVal = results.get(key);
        if (memoizedVal != null) {
            return memoizedVal;
        }
下一个优化级别是具有n X sum的2D表，其中n是集合中元素的数量。 

从递归关系很容易理解，(arr, sum - arr[i], i)转换为同一行中的DP[sum-arr[i]]。（因为i相同）

[(arr, sum, i - 1)转换为DP[i-1]（sum列中的上一行）。

具有如下所示的二维矩阵的完整解决方案。

public static int countWaysDP2D(int[] arr, int sum) {
    int[][] table = new int[arr.length][sum + 1];
    table[0][0] = 1;

    for (int i = 1; i <= sum; i++) {
        table[0][i] = 0;
    }

    for (int j = 1; j < arr.length; j++) {
        table[j][0] = 1;
    }

    for (int i = 1; i < arr.length; i++) {
        for (int j = 1; j <= sum; j++) {
            int sumWithI = j - arr[i-1] < 0 ? 0 : table[i][j - arr[i-1]];
            int sumWithoutI = table[i - 1][j];
            table[i][j] = sumWithI + sumWithoutI;
        }
    }
    return table[arr.length - 1][sum];
}
但是给定的here in method 2灵魂仅使用一维数组，如下所示

public static int countWaysDP1D(int[] arr, int sum) {
    int[] table = new int[sum + 1];
    table[0] = 1;

    for (int i = 0; i < arr.length; i++) {
        for (int j = arr[i]; j <= sum; j++) {
            table[j] += table[j - arr[i]];
        }
    }
    return table[sum];
}
仅使用一维数组的背后逻辑是什么？我测试了许多输入值，结果与2D数组相同。 2D阵列解决方案如何转换为1D阵列？

我正在学习动态编程，并遇到了这个著名的硬币兑换问题。解决这个问题的递归关系由countCoinsChangeRec（arr，sum-arr [i]，i）+ ...

Answer 1

具有一维数组的解决方案只是重用您保留在单独行中的空间。这是可能的，因为不再使用那些“较旧”的行。