硬币兑换（动态规划）
但是我们不能这样做吗：（V是给定的可用硬币的排序集，i和j是它的下标，Vj是给定的最高价值硬币）
C[p,Vi,j] = C[p,Vi,j-1] if Vj > p
= C[p-Vj,Vi,j] + 1 if Vj <=p
我写的东西有什么问题吗？虽然解决方案不是动态的，但不是更有效吗？
共有2个答案
你所写的类似于贪婪算法，它只在特定条件下有效。（参见-如何判断贪婪算法是否足以找到最小硬币变化？）。
此外，在您的版本中，您实际上没有在循环中使用Vi，因此这只是浪费内存
考虑<代码> p＝6，v= { 4, 3, 1 } < /代码>。你会选择4,1,1而不是3,3，因此3硬币而不是最佳2。
-
我编写的代码使用动态规划解决了基本的硬币兑换问题，并给出了进行兑换所需的最小硬币数量。但是我想把每个硬币的数量存储在最小的数字里。 我试图做的是初始化数组，就像散列一样，只要找到，它就会增加的数量，即。但这并不是我想要的方式，因为它每次发现对应于时都会添加硬币。因此，在最终答案中，数字不是硬币的最终计数。 代码如下：
-
在硬币系统C={c1，c2，…ck}中，应改变给定的数量x，以使每个硬币ci具有给定的重量wi。我们想计算可能变化的总重量。两种变化是不同的，如果他们包含在不同的顺序相同的硬币。 如何给出上述问题的动态规划递归？我知道最小硬币兑换问题的递归（即C（x）=min{C（x-C）1 for x
-
问题-你会得到不同面额的硬币和总金额。写一个函数来计算你需要的最少数量的硬币来组成这个数量。那里有无限的硬币供应。 我的方法——我遵循了自上而下的方法，但是使用map stl进行记忆，我得到了TLE。请帮助找出误差和估计时间复杂度。 这是我的密码-
-
我一直在使用动态规划研究硬币兑换问题。我尝试制作一个数组fin[]，其中包含索引所需的最小硬币数，然后打印它。我已经写了一个代码，我认为应该给出正确的输出，但我不明白为什么它没有给出准确的答案。例如：对于输入：4 3 1 2 3（4是要更改的金额，3是可用硬币的类型，1 2 3是硬币值列表）输出应该是：0 1 1 2（因为我们有1,2,3作为可用硬币，需要0个硬币更改0，1个硬币更改1，1个硬币更
-
http://uva.onlinejudge.org/external/6/674.html我正在努力解决这个问题。不过，请注意，这不是最小硬币更换问题，它要求我使用50, 25, 15, 10, 5和1美分硬币制作N美分的不同方法。它相当简单，所以我做了这个函数： 同样简单的是添加动态编程和备忘录： 然而，这些都不够快-我需要自下而上的动态规划，但我在编码它时遇到困难，即使在算法学家的帮助下-h
-
我很难理解这个问题背后的逻辑，这是经典的动态规划问题 我知道递归是如何工作的，比如拿不拿mth硬币。但我不明白这两个州之间的关系。 例如 这个问题可能很愚蠢，但我还是想知道，这样我才能更好地理解。谢谢