递归的进一步学习-动态规划之最少硬币问题

阶乘和斐波那契数列相信各位都很熟悉,典型的教材式递归例子,因为简单退化为循环也没啥难度。不过依赖于递归的问题并不都是那么简单的,比如最少硬币问题,需要称为动态规划(DP)的方式来实现。
所谓动态规划个人理解就是缓存一下递归的结果。比如斐波那契数列,简单的实现方式是:

假如计算fib(5),事实上计算了一次fib(4),两次fib(3),三次fib(2),四次fib(1),两次fib(0),换句话说,重复计算了(1 – 1) + (2 – 1) + (3 – 1) + (4 – 1) + (2 – 1)有7次之多。理想情况下每个fib(n)只要计算一次。改进方法很简单,增加cache,其实就是简单的映射数组:

这里用0代表fib值未知。

经过上述改造后,一般递归的深度优先逻辑会“缓存”前一次计算的值,大大降低了深层次的计算量。

现在考虑另外一个问题:最少硬币问题。假设你有1,5,10,25,50五种硬币,现在要你支付63,最少需要多少硬币?
问题看似很简单,不断用最大可能的硬币组合即可,63 = (50 + 10 + 1 x 3),即5个硬币。
现在假设你有1, 5, 10, 21, 50这五种硬币,仍旧让你支付63,最少需要多少硬币?如果仍旧按照原有方法计算,答案是5个,但实际上最佳的组合是3个21硬币。更明确点讲,原有方法其实是贪心算法,但是某些时候不会得到最佳的解。
因为问题可以分解为让你支付62和1,分别需要多少硬币的两个问题,这些问题还可以继续分成61 + 1或者52 + 10等等。你可以想想一下,计算63的最少硬币数,实际要尝试1-62所有的最少硬币数,或者说这些都是63的子问题。这和斐波那契数列是不是很像?斐波那契数列的公式是:

最少硬币问题的公式可以归纳为:

下面的5个公式,可以合并为min_coin(n – c) + 1 if n >= c and c in coins
有了公式,我们就可以开始计算了。代码如下:

看起来似乎很简单,但是UNKNOWN和UNAVAILABLE是什么?UNKNOWN和之前斐波那契数列的0很像,就是表示未确定值的意思。而UNAVAILABLE是无法用给定的硬币算出需要的amount,比如你无法使用加法和硬币[10, 20]算出35来。
公开方法minCoin负责初始化动态规划(DP)的缓存和设置amount为0时最少硬币数为0。私有方法是实际的递归逻辑。初始认为无法算出指定的amount。然后遍历可用的coin,如果当前coin == amount,根据经验,代表最少硬币数就是1,否则在amount大于当前硬币的时候,计算amount减去当前硬币的最少硬币数,假设这个差值无法得到可用的最少硬币组合,那么就跳过这个硬币,否则在最少硬币未确定或者当前方案总硬币数(加上当前硬币的个数1)小于其他方案时设置最少硬币数,最后是回写最少硬币数缓存。

整体来说,动态规划并不是很难,特别是在你找到公式之后。不过实现上的一些细节问题还是要到实现时才能了解。