动态规划——硬币找零问题

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/

谢谢。我去的每个网站都只解释了解决方案的工作原理，却没有解释其他解决方案为什么不起作用。

- zc917

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，基于情况）。再次应用相同dp[2]=dp[1]=1。因此，总共得到答案为3，而实际上只有2个解（（1,3）和（1,1,1,1））。这是因为您的第二种方法将（1,3）和（3,1）视为两种不同的解。您的第二种方法适用于顺序有关的情况，这也是一个标准问题。 现在针对您的第二个问题，您说最小面额的数量可以通过DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1找到。那么这是正确的，因为在寻找最小面额时，顺序或不顺序并不重要。为什么这是线性/1-D DP，尽管DP数组是1-D，但每个状态最多依赖于m个状态，而不像您的第一个解决方案，数组是2-D，但每个状态最多只依赖于2个状态。因此，在两种情况下，运行时间（状态数*每个状态所依赖的状态数）都是相同的，即O(nm)。因此，两者都是正确的，只是您的第二种解决方案节省了内存。因此，您可以通过1-D数组方法或通过使用递归dp(n,m)=min(dp(m-1,n),1+dp(m,n-Sm))来找到它。（只需在第一次递归中使用min） 希望我解决了疑虑，如果仍有不清楚的地方，请随时发布。

- advocateofnone

Answer 2

这是使用动态规划解决硬币找零问题的非常好的解释。

代码如下：

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

- Pritam Banerjee