在动态规划问题中,有一个很常见的问题就是最少硬币兑换。假设当前有面额为1,2,5元的硬币,然后给你一定额度,要求你将额度兑换成等值硬币,并要求兑换硬币的数量要最少。...例如给定的额度为9元,那么兑换的方法有[5, 1, 1, 1, 1], [5,2,2], [2,2,2,1],很显然第二种兑换方法最好。
如果你了解前面描述的动态规划方法,那么这个问题的处理不难。...,因此得到问题的解,那么从根节点到当前节点对应的数值就是所兑换的硬币数值。...同时需要注意的是,并发每个节点都能再延伸出下层节点,例如第二层的节点4因为不能再使用面值为5的硬币兑换,因此它不能产生对应分支。...我们看一个具体实例,假设要兑换的面额有6,那么对应的方案有:
1,1,1,1,1,1
1,1,1,1,2
1,5
2,2,2
从实例上看,所有方案的集合有一些特点:某一些方案的集合包含了硬币1,某些方案的集合不包含