硬币兑换，重新审视动态规划
我很难理解这个问题背后的逻辑，这是经典的动态规划问题
Coin Change is the problem of finding the number
of ways of making changes for a particular amount of cents, n,
using a given set of denominations d1,d2,..dm;
我知道递归是如何工作的，比如拿不拿mth硬币。但我不明白这两个州之间的关系。
例如
C(N,m)=C(N,m-1)+C(N-dm,m)
^
|
这个问题可能很愚蠢，但我还是想知道，这样我才能更好地理解。谢谢
共有1个答案
嗯，你的州写得不对！硬币兑换：
设C（i，j）表示仅使用i硬币（从i到1）形成j的方法的数量。
现在要得到一个递归函数，你必须定义转换或状态变化，或者可能只是用较低的值来表达给定的表达式！！
我可以用两种独立的方式来表示这种状态
1） 让我们拿起第i枚硬币，然后会发生什么？如果不允许重复，我需要面额为j的面额[I]和I-1硬币。i、 e.C（i，j）=C（i-1，j面额[i]）
但是等待，我们错过了一些方法，即当我们不采取当前的硬币
2） C（i，j）=C（i-1，j）
现在，由于它们都是独立的和详尽的，这两种状态构成了所有的方式！！！
C（i， j）=C（i-1， j）C（i-1， j-面值[i]）
当允许重复时，我会离开复发！
-
我编写的代码使用动态规划解决了基本的硬币兑换问题，并给出了进行兑换所需的最小硬币数量。但是我想把每个硬币的数量存储在最小的数字里。 我试图做的是初始化数组，就像散列一样，只要找到，它就会增加的数量，即。但这并不是我想要的方式，因为它每次发现对应于时都会添加硬币。因此，在最终答案中，数字不是硬币的最终计数。 代码如下：
-
但是我们不能这样做吗：（是给定的可用硬币的排序集，和是它的下标，是给定的最高价值硬币） 我写的东西有什么问题吗？虽然解决方案不是动态的，但不是更有效吗？
-
在硬币系统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