使用的贪心算法解决的凑硬币问题，有些情况下可以得出正解： 比如后一个钱币面值没有达到前一个钱币面值的2倍时。 但对于某些情况来说得出的解是错误的： 比如，有3种面值分别为3元，5元，7元。 （1）至少用几张纸币能凑够10元？我的直觉告诉我先选面值最大的，7元一张，然后再选面值5元的时候发现超额了（7+5>10），因此我们选3元一张，最少用2张纸币就能凑够10元，这个时候可以得出正解。这个方法容易想出来，抽象一点可以叫贪心算法（每次都选当前看来最好的选择，不从整体最优考虑）， （2）那么至少用几张纸币能凑够8元呢？如果还按照贪心算法来解的话会得不到解。因为先选一张7元，然后再选5元（7+5>8）不行，换选3元（7+3>8）还不行。但是仔细看会发现5元+3元不是8元吗，怎么会无解。所以贪心算法解这个问题是不行的。

到这里我们发现用贪心算法会出现两个问题 1）本来有解用贪心法算出来却无解，例如上例 2）至少用几张纸币能凑够8元？（2）算出来的解不是最优解，例如有 1元，7元，9元，10元四种面值的纸币，要凑18元 ，贪心算法会给出答案需要3张（10元1张，7元1张，1元1张），但是我们可以明显看出 2张（两张9元）也可以。

那么问题出在了哪里？在这里用贪心算法是有条件的——后一个的权值（这里就是纸币面值）是前一个的2倍或以上才可以使用，这里10不到9的两倍。贪心算法不是对所有问题都能得到整体最优解。关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。在这里我们先选择了10元，在第二步的时候9元就选择不了了（10+9>18了），所以会错过9+9这个最优解。所以说贪心算法在对问题求解时，总是做出在当前看来是最好的选择，不从整体最优考虑。

如何用动态规划算法解题。可能你已经不耐烦了，那么先上一个此问题递推公式（也可以叫做动态转移方程）：（注:v[i]表示可以使用的纸币的面额组成的数组，dp[m]表示要凑m元至少需要多少张纸币。）

dp[m] = min(dp[m-v[i] ]+1,dp[m]) 那么这个方程怎么得来的呢？我们先了解一下DP（Dynamic Programing）的基本原理：首先，找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。不明白这个概念没关系，我们以上面的例子为例来分析一下——如果我们有4种面值分别为1元，3元，5元，7元的纸币，那么至少需要几张纸币就能凑出8元？

在分析这个问题之前先来思考一个问题，至少用多少张纸币能凑够m（表示money）元(m=0，v[i] 表示第i个硬币的面值，方程的含义是拿出一个面值为 v[i] 的硬币后，凑够 m-v[i] 元至少需要的硬币数目（dp[m-v[i] ]）+1和凑够m元至少需要的硬币数目（dp[m]）相比较，取较小的存入dp[m]。

这里可能就会有人问了，为什么还要和dp[m]比较后再存入dp[m]，正如上面的例子，因为我们在凑够m元时，可能有多种可行的方案，我们要比较出哪一种方案所需硬币数目最小。例如在4种硬币1、3、5、7元凑8元的时候会有三种方案，1）8个1元；2）3+5元；3）1+7元。我们得从中找到我们所要的答案。（如果用贪心算法的话可能会错过最优解）。 以上分析全部摘录于博客https://www.cnblogs.com/hitwhlm/p/9795344.html 我觉得该博主对动态规划算法讲的比较细，因此对原作者的文字稍加修改后直接摘录到此，希望哪天自己糊涂了也能有个出处。 下面代码由本人完成，下面上代码