动态规划换币问题

Question

我在理解各种问题的动态规划解决方案方面存在问题，特别是硬币兑换问题：

“给定一个值N，如果我们想换N美分，并且我们有无限多个S={S1，S2，…，Sm}值的硬币，我们可以用多少种方式来换？硬币的顺序并不重要。

例如，对于N=4和S={1,2,3}，有四种解决方案：{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]是硬币可以获得的方式数量。我觉得这听起来合乎逻辑，但它给出了一个错误的答案。为什么在这个问题中需要硬币的第二维度，而在最小数量问题中不需要？

与问题的联系：

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

提前谢谢。我访问的每个网站都只解释解决方案是如何工作的，而不是其他解决方案不工作的原因。

Answer 1

这是一个很好的解释硬币兑换问题使用动态规划。

代码如下：

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

Answer 2

>

让我们先谈谈方式的数量，DP（m，n）=DP（m-1，n）DP（m，n-Sm）。这确实是正确的，因为要么你可以使用mth面额，要么你可以避免它。现在你说我们为什么不把它写成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）。所以两者都是正确的，只是你的第二个解决方案节省了内存。因此，您可以通过一维数组方法或通过使用递归dp（n，m）=min（dp（m-1，n），1dp（m，n-Sm））的二维方法找到它。（在第一次复发中使用min）

希望我澄清了疑问，如果还有什么不清楚的话就发帖子。