箱猫日和

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

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

public int fib(int n) {
  if(n == 0 || n == 1) return 1;
  return fib(n - 2) + fib(n - 1);
}

假如计算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，其实就是简单的映射数组：

public int fib(int n) {
  if(fib_cache[n] > 0) return fib_cache[n]; // fib_cache = [1, 1, 0 ... 0]
  return (fib_cache[n] = fib(n - 2) + fib(n - 1));
}

这里用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的子问题。这和斐波那契数列是不是很像？斐波那契数列的公式是：

fib(n） = 0                       if n = 0 or n = 1
          fib(n - 2) + fib(n - 1)

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

min_coin(n) = 0                    if n = 0
              min_coin(n - 1)  + 1 if n >= 1  (coin 1)
              min_coin(n - 5)  + 1 if n >= 5  (coin 5)
              min_coin(n - 10) + 1 if n >= 10 (coin 10)
              min_coin(n - 21) + 1 if n >= 21 (coin 21)
              min_coin(n - 50) + 1 if n >= 50 (coin 50)

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

private static final int UNAVAILABLE = -1;
private static final int UNKNOWN = -2;
private int[] minCoinCache;

public int minCoin(int[] coins, int amount) {
  minCoinCache = new int[amount + 1];
  Arrays.fill(minCoinCache, UNKNOWN);
  minCoinCache[0] = 0;
  return doMinCoin(coins, amount);
}

private int doMinCoin(int[] coins, int amount) {
  if (minCoinCache[amount] != UNKNOWN) return minCoinCache[amount];
  int min = UNAVAILABLE;
  for (int c : coins) {
    if (amount == c) {
      min = 1;
    } else if (amount > c) {
      int _min = doMinCoin(coins, amount - c);
      if (_min == UNAVAILABLE) continue;
      _min += 1; // add current coin
      if (min == UNAVAILABLE || _min < min) min = _min;
    }
  }
  minCoinCache[amount] = min;
  return min;
}

public static void main(String[] args) {
  MinCoinDP dp = new MinCoinDP();
  System.out.println(dp.minCoin(new int[] {50, 21, 10, 5, 1}, 63));
  System.out.println(Arrays.toString(dp.minCoinCache));
}

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

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

xnnyygn