达成硬币兑换问题动态规划解决方案的思考过程 [英] Thought process for arriving at dynamic programming solution of Coins change problem

问题描述

我正在学习动态编程，并遇到了这个著名的硬币更改问题。

I am learning dynamic programming and came across this famous coins change problem.

解决此问题的递归关系由

The reccurence relation to solve this problem is given by

countCoinsChangeRec（ arr，sum-arr [i]，i）+ countCoinsChangeRec（arr，sum，i-1）;

最简单的优化方法问题是通过存储子问题的解。因此，我为每个（sum，i）的值维护了一个 Map 。

The simplest way to optimize the problem is by storing the solutions of sub problem. So I maintained a Map for each value of (sum,i). There by not solving same problems again.

        String key = sum + ":" + i;    
        Integer memoizedVal = results.get(key);
        if (memoizedVal != null) {
            return memoizedVal;
        }

下一级别的优化是使用的2D表n X sum 其中n是集合中元素的数量。

Next level of optimization is having a 2D table of n X sum where n is number of elements in the set.

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

It is easily understandable from reccurence relation that (arr, sum - arr[i], i) translates to DP[sum-arr[i]] in same row.(Because i is same)

和（ar，sum，i-1）转换为 DP [i-1] （ sum 列中的上一行）。

And (arr, sum, i - 1) translates to DP[i-1] (Previous row in sum column).

具有2D矩阵的完整解决方案，如下所示。

Complete solution with 2D matrix shown below.

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];
}

但是此处方法2 仅使用一维数组，如下所示

But the soultion given here in method 2 uses just 1D array as shown below

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数组相同。二维数组解决方案如何转换为一维数组？

What is the logic behind using just 1D array? I tested with many input values and results were same as 2D array. How is 2D array solution converted to 1D array?

我的意思是所有初始条件都去了哪里？（第0行和第0列）

I mean where are all the initial conditions gone?(0th row and 0th column)

对于 j th循环，为什么要从数组中的 j 个元素进行迭代，直到 sum 递增 1 ？很难想象所有这些。有人可以逐步解释这种转换吗？

For jth for loop, why does it iterate from jth element in the array till sum incremented by 1? It is really hard to visualize all of that. Can somebody explain this transformation step by step?

推荐答案

从递归关系 countCoinsChangeRec（arr，sum- arr [i]，i）+ countCoinsChangeRec（arr，sum，i-1）; ，很明显，您需要尺寸为 len（arr）x的二维数组/表（sum + 1）存储结果。我们将从表格的左上方到右下方依次填充表格，我们的答案是右下方单元格的值。您需要两个值来填充表 table [i，sum-arr [i]]和table [i-1，sum] 的每个单元格。

From the recurrence relation countCoinsChangeRec(arr, sum - arr[i], i) + countCoinsChangeRec(arr, sum, i - 1);, it is obvious that you need 2D array/table of size len(arr) x (sum+1) to store the results. We shall fill the table sequentially from top left of the table to bottom right and our answer is the value of bottom right cell. You need two values to fill each cell of the table table[i, sum - arr[i]] and table[i - 1, sum].

请考虑填充一行-第0个单元格的起始值为1，所有其他单元格的起始值为0。要更新单元格，我们需要查找同一行内的 table [i，sum-arr [i]] 。对于表[i-1，总和] ，我们需要查找上一行。我们不需要任何其他行。因此，实际上我们只需要2行空间，就可以选择将其中一行视为上一行，而将另一行视为当前行被填充。

Consider filling a row -- 0th cell has value 1 and all other cells have a value of 0 at the start. To update a cell we need to lookup table[i, sum - arr[i]] which is within the same row. For table[i - 1, sum], we need to lookup the previous row. We don't need any other rows. So actually we only need 2 rows of space and we can alternatively treat one of the rows as previous row and other as current row being filled.

现在考虑使用仅2行的 2 x（sum + 1）表来解决此问题。考虑第1行是正在填充的当前行，第0行是已经填充的前一行。说arr = [2，3，7]。因此，您按如下所示填充行1。

Now consider using 2 x (sum+1) table with just 2 rows to solve the problem. Consider row 1 is the current row being filled and row 0 is previous row which was already filled. Say arr = [2, 3, 7]. So you fill the row 1 as follows.

table[1, 0] = table[0, 0]  
table[1, 1] = table[0, 1]
table[1, 2] = table[0, 2]
table[1, 3] = table[1, 0] + table[0, 3]
table[1, 4] = table[1, 1] + table[0, 4]
table[1, 5] = table[1, 2] + table[0, 5]
...

观察上面的方程式后，另一种计算行1的方法将第0行复制到未填充的第1行，然后按如下所示填充第1行

After observing above equations, another way to calculate the row 1 is copying row 0 onto unfilled row 1 and then filling row 1 as follows

Copy row 0 onto row 1

table[1, 3] += table[1, 0]
table[1, 4] += table[1, 1]
table[1, 5] += table[1, 2]

不是将行0复制到未填充的行1中，而是可以重用行0本身。因此，该算法的最终空间有效化身为-占用一行大小（sum + 1）。将row [0] = 1分配为基本条件。填充第0行或任何其他行的方式没有任何区别，因为我们现在进行的唯一查找位于上述同一行内。

Instead of copying row 0 onto unfilled row 1, we can re-use row 0 itself. So the final space efficient avatar of the algorithm is - take a single row of size (sum+1). Assign row[0] = 1 as base condition. There is no difference in how we fill 0th row or any other row because the only lookups we make now is within the same row as shown above.

// Pseudo code
create row of size (sum+1) 

row[0] = 1 // base condition

fill rest of the row with zeros

for element in arr:   /* for (int i = 0; i < arr.length; i++) */
    from column j where j - element >= 0 to end of row /* int j = arr[i]; j <= sum; j++ */
    row[j] += row[j-element]

return last element of row

这篇关于达成硬币兑换问题动态规划解决方案的思考过程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！