很多程序的目的在数值优化。象计算两地之间的最短距离，一个点集的最佳拟合曲线，符合某些条件的最小集合等。这些问题有很多的求解方法，本节的目标就是向你展示不同的问题解决策略。动态规划就是优化问题的解决方法之一。

找零问题是数值优化的经典问题之一，假设你是一个自动售货机厂商的程序员，公司决定，为每次找交易的找零，计算需要的最小的硬币数量，从而实现流程化。如果一个顾客投入了1美元，买了37美分的东西，需要最小的硬币是多少？答案是6个：2个25美分（译者：不知道作者为什么不使用50美分的硬币），1个10美分，3个1美分。答案怎么来的？我们从最大的硬币开始，尽可能多地使用大额硬币，直到余额不够这个面值，然后再尽可能多地使用第二面额的硬币，以此类推。这种方法叫做“贪婪方法”，因为我们总是对正在计算的问题，作出当前看来最好的结果。

贪婪方法在美国硬币问题上回答正确，但如果你的公司要把自动售货机出口到Lower Elbonia(译注：Elbonia 是系列漫画 Dilbert 中一个杜撰的原东欧共产主义国家。Lower Elbonia 指这国家的南部。)，那里除了平时所用的1，5，10和25美分硬币，还有一种21美分的。这时贪婪算法就失灵了，因为它仍然会算出6个硬币，但正确答案是3个21美分的硬币。

我们在研究找出一种确保正确答案的方法。既然本章是在谈递归，你也许想到用递归解决。先说递归的基点开始。

如果我们要找的零钱，正好是某个硬币的面值，那就简单了，一个硬币。

如果找零和手上的硬币都对不上号，那么答案是以下四种情况的最小值：

从要找的零钱中拿掉一个1分币，计算余额最少需要多少硬币，然后加上这个硬币

从要找的零钱中拿掉一个5分币，计算余额最少需要多少硬币，然后加上这个硬币

从要找的零钱中拿掉一个10币，计算余额最少需要多少硬币，然后加上这个硬币

从要找的零钱中拿掉一个25分币，计算余额最少需要多少硬币，然后加上这个硬币。

也就是按以下公式计算：

以上算法的实现如下。第三行是查检基点，就是说看一下找钱是否就是某个硬币的面值，如果不是，就把找钱的值减去每种硬币的面值，然后依次递归计算。第6行加了一个过滤，就是只比较面币比找钱小的硬币，递归过程也一直在降低找钱的数值。第7行进行递归调用，注意这一行我们对硬币数量有一个加1的的过程，因为后面的递归是减少一个硬币的递归，趋向基点的过程。

Listing 7

def recMC(coinValueList,change):

   minCoins = change

   if change incoinValueList:

     return 1

   else:

      for i in [c for c incoinValueList if c <= change]:

         numCoins = 1 +recMC(coinValueList,change-i)

         if numCoins <minCoins:

            minCoins = numCoins

   return minCoins

print(recMC([1,5,10,25],63))

可惜的是，上面算法效率非常之差，实际上，找到6毛3分钱的硬币数量，进行了67,716,925次递归。为了帮助理解，图5显示了一个较小的为了找到2毛6的硬币377次函数调用的过程。

图中，每个节点对一次recMC函数的调用。节点上的标签表示当前求解的找钱数量，箭头上的标签表示减掉的那个硬币。跟踪图形可以得到任意的硬币组合。主要问题在于重复计算太多了，例如图中15分的数值至少有3次计算，每次计算包括52次函数调用，很明显我们很多时间浪费在重复计算上。

减少计算量的关键是记住已经得到的中间结果。一个简单方法是把已经计算出最小值的找钱保存在表里，每次计算之前，先查一下表看看这个结果是否已知。如果已知就直接套用不再计算。下面是优化的算法：

defrecDC(coinValueList,change,knownResults):

  minCoins = change

  if change in coinValueList:

     knownResults[change] = 1

     return 1

  elif knownResults[change] > 0:

     return knownResults[change]

  else:

      for i in [c for c in coinValueList if c <= change]:

        numCoins = 1 + recDC(coinValueList, change-i,

                              knownResults)

        if numCoins < minCoins:

            minCoins = numCoins

            knownResults[change] = minCoins

  return minCoins

print(recDC([1,5,10,25],63,[0]*64))

注意第6行增加一个测试表中是否包括了计算结果，如果没有，计算并保存到表中。这样优化后，计算6毛3分钱的最小硬币数量，只用了221次调用。

虽然这个结果是正确的，但似乎有点黑客的味道。并且如果查看一下knownResults列表，会发现有太多的洞（0值），事实上上面的算法不能称之为动态规划，只是利用了记忆或缓冲的做法优化了我们程序的性能。

真正的动态规划算法要更加系统化地逼近问题答案。解决方法从一个硬币开始，逐步靠近我们要计算的数值，在中间过程中每个找钱数字我们都得到了所需的最少硬币数量。

我们来研究一下，对于11分的找钱计算最小需要的硬币数量，怎样填表。如图4所示的过程，从1分开始，唯一可能是1个硬币。下一行显示的是1分和2分的情况，当然，2分也只有一个答案就是2个硬币。从第5行开始事情变得有意思起来，我们有2个选择，是5个1分币或1个5分币。哪个方案好？我们查表发现对要找4分钱的情况是4个硬币，加上1个就5个硬币，或者是0个5分币加上1个5分币为1个硬币。因为最小值是1，我们在表中填上1。继续向前到表的末端考虑11分的情况，图5所示为我们要考虑的3个选项。

1. 1个1分币加上10分找钱的最小硬币数量（1个）
2. 1个5分币加上6分找钱的最小硬币数量（2个）
3. 1个10分币加上1分找钱的最小硬币数量（1个）