def dc(num,dic): # 分而治之，最少的钱数组合 kind = [100,50,20,10,5,1] # 钱的面额 if num == 0: return dic else: for k in kind: if num>=k: num = num - k if k in dic: dic[k]+=1 else: dic[k] = 1 return dc(num,dic) dic = dc(63,{}) print(dic)
分析：找零钱的时候，先找零最大面值的钱，比如63块钱，先找零50，剩余13，对于剩余的零钱，再次比对，再找出最大面值的钱10，剩3块，以此类推。
原文：https://www.cnblogs.com/wztshine/p/13031339.html