我在理解各种问题的动态编程解决方案时遇到问题，特别是硬币找零问题：
“给定值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/
提前致谢。我访问的每个网站仅说明该解决方案的工作原理，而不说明其他解决方案为何不工作。
希望我清除了疑问，如果仍然不清楚，请发帖。
