动态编程硬币更改问题

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代表每种硬币面额。

为什么第一个需要二维数组，而第二个需要1-D数组呢？为什么更改方式的最优子结构不是“ DP [i] = DP [i-d1] + DP [i-d2] + ... DP [i-dn] ”，其中DP [i]是我可以通过硬币获得数量的方法的数量。这对我来说听起来合乎逻辑，但会产生错误的答案。为什么在这个问题中需要硬币的第二维，而在最小数量问题中却不需要？

问题链接：

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

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

Answer 1

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。因此，总的来说，当答案应为2（（1,3）和（1,1,1,1））时，您将获得3的答案。之所以如此，是因为您的第二种方法将（1,3）和（3,1）视为两个不同的解决方案。您的第二种方法可以应用于顺序很重要的情况，这也是一个标准问题。

2. 现在，对于第二个问题，您说最小面额可以通过DP [i] = Min {DP [i-d1]，DP [i-d2]，... DP [i-dn]} + 1求出。嗯，这是正确的，因为寻找最小面额，顺序或无顺序都无关紧要。为什么是线性/一维DP，虽然DP数组是一维的，但每个状态最多取决于m个状态，这与第一个解决方案中数组为2-D但每个状态最多取决于两个状态的情况不同。因此，在两种情况下，运行时间（状态数*每个状态所依赖的状态数）都是相同的，即O（nm）。因此，两者都是正确的，只是您的第二种解决方案可以节省内存。因此，您可以通过一维数组方法找到它，也可以通过使用递归 dp（n，m）= min（dp（m-1，n），1 + dp（m，n-Sm））来找到它。。（只需在首次复发时使用min）

   
   希望我清除了疑问，如果仍然不清楚，请发帖。