该算法是否涵盖了寻找一笔金额的最小硬币兑换的所有情况？
我正在努力解决最小硬币兑换问题。问题是：给定一个值V，如果我们想改变为V美分，并且我们有无限量的C={C1，C2，...，Cm}值的硬币，做出改变的最小硬币数量是多少？
我建议的算法是：
从数组arr[1..V]开始，其中V是值：
>
对于i:1中的所有值。。。V：计算为“i”值进行兑换所需的最小硬币数量。2.1. 这可以通过以下方式完成：对于所有j:1。。。。（i-1）arr[i]=min（arr[i]，arr[j]arr[i-j]）；
返回arr[V]；
这一逻辑是否有缺陷，或者是否涵盖了所有情况？大多数DP解决方案都使用了二维阵列，我不明白为什么它们会使用O（n^2）内存空间，如果这存在并且是正确的话。谢谢你。
共有1个答案
对于无法获得某些值的情况如何？
即我们有硬币{5,6,7,8,9}，我们不能使值1,2,3,4，你应该初始化所有的值！=将单元格妖魔化为无穷大常数或类似的东西。
现在由于大多数人使用O（n^2）内存的原因：
这个问题有各种不同的口味，最常见的一种是每个硬币只能使用一次，在这种情况下，使用状态dp[i][j]-min的硬币，在考虑第一个i硬币后，总和为j，对大多数人来说似乎更容易理解，即使这也可以通过O（n）内存实现（只是向后循环）
-
给定一个值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}。
-
给定一组面额和所需的总和我必须找到最低数量的硬币使该总和以及硬币的数量为每个面额 请帮忙！！
-
问题-你会得到不同面额的硬币和总金额。写一个函数来计算你需要的最少数量的硬币来组成这个数量。那里有无限的硬币供应。 我的方法——我遵循了自上而下的方法，但是使用map stl进行记忆，我得到了TLE。请帮助找出误差和估计时间复杂度。 这是我的密码-
-
在研究硬币更换问题后，我尽力实施解决方案。到目前为止，我的代码打印了给定金额所需的最低硬币数量。然而，它并不打印出每种硬币面额所需的数量。这是我的代码目前的样子： 我只是很困惑如何/在哪里填充numOfCoins[]。
-
我在理解动态规划中的硬币兑换问题时遇到了一个小问题。简单地说，我必须用最少数量的硬币来兑换一笔钱。 我有n种面值为1=v1的硬币
-
如果每枚硬币的数量是无限的，那么复杂性是O（n*m），其中是总变化，是硬币类型的数量。现在，当每种类型的硬币都受到限制时，我们必须考虑剩余的硬币。我设法使它与的复杂性使用另一个大小的，所以我可以跟踪每个类型的剩余硬币。有没有一种方法可以让复杂性变得更好？编辑：问题是计算进行精确给定更改所需的最少硬币数量以及我们使用每种硬币类型的次数