最顶层是要兑换的面额,然后根据不同硬币数值进行兑换后得到第二层,例如当前硬币数值为[1,2,5],面额为9,那么分别兑换硬币1,2,5后所得数额分别为8,7,4,接下来分别针对第二层3个节点进行相应操作...,因此得到问题的解,那么从根节点到当前节点对应的数值就是所兑换的硬币数值。...同时需要注意的是,并发每个节点都能再延伸出下层节点,例如第二层的节点4因为不能再使用面值为5的硬币兑换,因此它不能产生对应分支。...33)
solution.coin_changing()
上面代码运行后结果如下:
[5, 5, 5, 5, 5, 5, 2, 1]
这个问题有一个变种,处理起来也不容易,那就是给定具体面额,要求算法给出总共有多少种不重复的兑换方案...例如给定数额3,存在的方案有,[1, 2], [2, 1], [1,1,1],但[1,2]和[2,1]是同一种方案,因此两者只能算做一种。