有时候,去便利店买几块钱的东西,但没有零钱,只能给他们一张100的,他们可能找给我一沓10块的和几枚硬币.我不喜欢这么多的零钱,要知道,钱越零散,散失地就越快,我希望找给我的零钱张数最少.
通过这样的递归,可以找出所有可能的解来,这样就可以找到最优解来了.不过该方法效率不高,因为存在大量冗余的计算,比如要找出60元,中间需要计算59,要计算59则一定需要计算58...而且这些计算要重复多次,这种情形称为"递归爆炸".这里很像使用递归来求解Fibonacci数列一样,存在很大的效率问题.在优化Fibonacci数列的计算时,一种方法是将计算过的值存放在一个数组里,以供重复使用,这里也可以采用这样的思路.
这个方法属于动