问题描述：给你六种面额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）了。看起来要比递归麻烦很多，但是结果却是这种方式更为简单，因为其避免了递归中大量的栈的使用。
下一篇再写。
网友评论