1、引入（找零兑换问题 ）
假设你为一家自动售货机厂家编程序，自动售货机要每次找给顾客最少数量硬币； 假设某次顾客投进$1纸币，买了ȼ37的东西，要找ȼ63，那么最少数量就是： 2个quarter（ȼ25）、 1个dime（ȼ10）和3个penny（ȼ1），一共6个
2、思想
首先是确定基本结束条件， 兑换硬币这个问题最简单直接的情况就是， 需要兑换的找零， 其面值正好等于某种硬币，如找零25分，答案就是1个硬币！ 其次是减小问题的规模， 我们要对每种硬币尝试1次， 例如美元硬币体系： 找零减去1分(penny)后，求兑换硬币最少数量（递归调用自身）； 找零减去5分(nikel)后，求兑换硬币最少数量 找零减去10分(dime)后，求兑换硬币最少数量 找零减去25分(quarter)后，求兑换硬币最少数量 上述4项中选择最小的一个。 最后，就是去调用函数自身。
3、代码实现
def recMC(coinValueList
,change
):
minCoins
= change
if change
in coinValueList
:
return 1
else:
for i
in [c
for c
in coinValueList
if c
<=change
]:
numCoins
= 1+recMC
(coinValueList
,change
-i
)
if numCoins
<= minCoins
:
minCoins
= numCoins
return minCoins
print(time
.time
())
print(recMC
([1,5,10,25],63))
print(time
.time
())
4、算法分析
递归解法虽然能解决问题， 但其最大的问题是： 极！ 其！ 低！ 效！ 对63分的兑换硬币问题，需要进行67,716,925次递归调用！ 如找零15分的，出现了3次！而它最终解决还要52次递归调用，很明显，这个算法致命缺点是重复计算。
5、算法改进
（1）分析
对这个递归解法进行改进的关键就在于消除重复计算，我们可以用一个表将计算过的中间结果保存起来，在计算之前查表看看是否已经计算过，这个算法的中间结果就是部分找零的最优解， 在递归调用过程中已经得到的最优解被记录下来，在递归调用之前，先查找表中是否已有部分找零的最优解，如果有， 直接返回最优解而不进行递归调用，如果没有，才进行递归调用 这种方法叫做“memoization（记忆化/函数值缓存） ”的技术，能提高递归解法的性能。
（2）代码实现
def recDC(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(time
.time
())
print(recDC
([1,5,10,25],63,[0]*64))
print(time
.time
())
