python穷举法硬币

以下是一个使用Python实现的硬币找零问题的穷举算法：

假设有一个人要找零50美分，他有无限多的1美分、5美分、10美分和25美分硬币，问他有多少种找零的方案？

def coin_change(n):
count = 0
for i in range(n//25+1): # 25美分硬币的数量
for j in range((n-i*25)//10+1): # 10美分硬币的数量
for k in range((n-i*25-j*10)//5+1): # 5美分硬币的数量
count += 1
return count

print(coin_change(50)) # 输出结果为49

在这个算法中，我们使用三个for循环来枚举25美分、10美分和5美分硬币的数量，然后计算出1美分硬币的数量。由于在最坏情况下，我们需要枚举50/5=10^10种可能的方案，因此该算法的时间复杂度为O(n^3)。