找零兑换问题的递归解法

硬币兑换问题，硬币包括1分、5分、10分、25分四种，给出找零金额，求兑换硬币最少数量。

初始递归解法步骤：

1. 确定基本结束条件：需要兑换的找零面值正好等于某种硬币（1，5，10，25）；
2. 减小问题规模：
   • 找零减去1分后，求兑换硬币最少数量（递归调用自身）；
   • 找零减去5分后，求兑换硬币最少数量；
   • 找零减去10分后，求兑换硬币最少数量；
   • 找零减去25分后，求兑换硬币最少数量；
     上述4项中选择最小的一个。

初始代码

import time
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.perf_counter())
print(recMC([1, 5, 10, 25], 63))
print(time.perf_counter())

初始结果

对63分的兑换硬币问题，需要进行67,716,925次递归调用，其中包括多次的重复计算，花费48秒才得到结果：6个硬币

递归解法改进

为了消除重复计算，可以将计算过的中间结果保存到一个表中，这个中间结果就是部分找零的最优解，在递归调用过程中已经得到的最优解被记录下来。
在递归调用之前，先查找表中是否已有部分找零的最优解：
- 如果有，直接返回最优解而不进行递归调用
- 如果没有，再进行递归调用

memorization（记忆化/函数值缓存）改进代码

import time

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

memo = [0] * 64
print(time.perf_counter())
print(recDC([1, 5, 10, 25], 63, memo))
print(time.perf_counter())
print(memo)

改进结果

得到结果只用了0.0002秒，效果显著。