算法硬币找零问题

win10+python3.8
问题：自定义硬币体系，最少找零数

#找零递归
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(recMC([1,5,10,21,25],63))

#找零加缓存改进
def recDC(coinValueList,change,knownResults):
    minCoins = change
    if change in coinValueList :
        knownResults[change] = 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  
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5658996.html