动态规划硬币找零问题

Question

我在理解各种问题的动态规划解决方案时遇到问题，特别是硬币找零问题：

"给定一个值 N，如果我们想找 N 美分，并且我们有无限供应的每个 S = { S1, S2, .. , Sm} 值的硬币，我们有多少种方法可以找零钱？硬币的顺序无关紧要。

例如，对于N = 4和S = {1,2,3}，有四种解决方案：{1,1,1,1}，{1,1,2}，{2,2 },{1,3}。所以输出应该是4。对于N = 10和S = {2, 5, 3, 6}，有五种解决方案：{2,2,2,2,2}，{2,2,3,3}， {2,2,6}、{2,3,5} 和 {5,5}。所以输出应该是 5."

这个问题还有另一种变体，解决方案是满足数量的最少硬币数量。

这些问题看起来非常相似，但解决方案却非常不同。

可能的改变方式的数量：最佳子结构是DP(m,n) = DP(m-1, n) + DP(m, n-Sm) 其中 DP 是所有硬币的解数，直到第 m 个硬币，数量 = n。

硬币的最小数量：为此的最佳子结构是 DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1 其中 i 是总量， d1..dn代表每个硬币的面额。

为什么第一个需要二维数组，第二个需要一维数组？为什么做出改变的方式数量的最佳子结构不是“DP[i] = DP[i-d1]+DP[i-d2]+...DP[i-dn]" 其中DP[i]是硬币获得i数量的方式的数量。这对我来说听起来合乎逻辑，但它会产生错误的答案。为什么在这个问题中需要硬币的第二个维度，但在最小数量问题中不需要？

问题链接：

http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

提前致谢。我访问的每个网站都只解释该解决方案的工作原理，而不解释其他解决方案为何不起作用。

Answer 1

先说路数，DP(m,n) = DP(m-1, n) + DP(m, n-Sm)。这确实是正确的，因为您可以使用第 m 个面额，也可以避免使用它。现在你说我们为什么不写成DP[i] = DP[i-d1]+DP[i-d2]+...DP[i-dn]。那么这将导致过度计数，让我们举一个例子，其中 n=4 m=2 和 S={1,3}。现在根据你的解dp[4]=dp[1]+dp[3]。（假设 1 是基本情况 dp[1]=1 ）。现在 dp[3]=dp[2]+dp[0]。（同样是 dp[0]=1 by base case）。再次应用相同的 dp[2]=dp[1]=1。因此，当它应该只是 2 （ (1,3) 和 (1,1,1,1) ）时，你得到的答案总共是 3。之所以如此，是因为您的第二种方法将 (1,3) 和 (3,1) 视为两个不同的 solution.Your 第二种方法可以应用于顺序很重要的情况，这也是一个标准问题。
现在你的第二个问题你说最小面额数可以由 DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1 找出。嗯，这是正确的，因为在寻找最小面额时，顺序或无顺序都没有关系。为什么这是线性/一维 DP，尽管 DP 数组是一维的，但每个状态最多取决于 m 个状态，这与您的第一个解决方案不同，数组是二维的，但每个状态最多取决于两个状态。因此，在这两种情况下，运行时间（状态数 * 每个状态所依赖的状态数）是相同的，即 O(nm)。所以两者都是正确的，只有你的第二个解决方案可以节省内存。所以要么你可以通过一维数组方法找到它，要么通过使用递归的二维方法找到它 dp(n,m)=min(dp(m-1,n),1+dp(m,n-Sm))。（只需在第一次重复时使用 min）

希望我消除了疑虑，如果还有不清楚的地方，请post。

Answer 2

This 很好地解释了使用动态规划的硬币找零问题。

代码如下：

public static int change(int amount, int[] coins){
    int[] combinations = new int[amount + 1];

    combinations[0] = 1;

    for(int coin : coins){
        for(int i = 1; i < combinations.length; i++){
            if(i >= coin){
                combinations[i] += combinations[i - coin];
                //printAmount(combinations);
            }
        }
        //System.out.println();
    }

    return combinations[amount];
}

动态规划硬币找零问题

Dynamic Programming Coin Change Problems

algorithm

dynamic-programming

coin-change