面额拼凑问题

问题描述：给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0-10000的非负整数）的不同组合的个数。 

以前碰到的很多问题我都是直接使用暴力穷举去做，只求能够做出来。这个问题我发现没那么容易，就算是想用暴力但是没有着力点，因为不知道如何确保穷尽。

看了别人的解答，发现需要用到动态规划思想。

从特殊到一般。假设你有1020元钱，如何拼凑？

1.1020元用这1、5、10、20、50、100这六种面额拼凑，等价于，1020元用不超过（<=）100元面额的纸币拼凑。

2.1020元用不超过（<=）100元面额的纸币拼凑，等价于，1020元用不超过（<=）50元面额（即不包含100）拼凑的组合数加上用包含100元面额拼凑的组合数。

注：包含100和不包含100合起来就是所有的组合数，保证穷尽。

3.1020用包含100元面额拼凑，等价于，920（抽出一张100，剩下的920）用不大于（<=）100面额拼凑。

结论：1020元用这六种纸币拼凑，等价于，1020元用不超过（<=）50拼凑组合数加上920元用不超过（<=）100拼凑组合数

这样就可以产生一个递推关系（1020,100）=（1020,50）+（920,100）。

递推图

有三个地方要注意。（由特殊到一般）

1.当面额为1时表示已经到了最小面额了，不可再分了，1020（任意一个正整数）用1组合而来只用一种情况，全部都是1块的。

2.当金额为0时，不可再分。那么0用小于20（或者任意其他面额）的面额组合都只用一种情况，一张都没有。

3.当金额小于当前面额时，例如（20,100），20用不大于（<=）100面额拼凑，必然不可能有100、50，所以这一步不应该继续分，而是将（20,100）化为（20,20）。一般情况下就是当数目小于当前面额时，先化简，直到数目不小于（>=）面额。

现在这道题思路就清晰了，直接的想法就是利用递归求解。

递归

但是问题出现了，由于递归本身的缺陷，其无法运行金额为10000（超过1000就很吃力了，到5000已经出不了结果了）的情况。

所以需要使用另一种方法，避免递归的缺陷。递归是从后往前推，那么我们可以从前往后推，就是将1到10000所有金额能用这六种面额拼凑的组合分别算出来，并保存。前面的算出来之后就可以用来算后面的。例如（1020,100）=（1020,50）+(920,100),算出了（1020,50）和（920,100）之后自然就可以算出（1020,100）了。看起来要比递归麻烦很多，但是结果却是这种方式更为简单，因为其避免了递归中大量的栈的使用。

下一篇再写。