1、递归
n = 0
def recursive_change(money,coins):
global n
if money == 0:
return 0
minNumCoins = float("inf")
for i in range(len(coins)):
if money >= coins[i]:
if money - coins[i] == 1:
n += 1
numCoins = recursive_change(money-coins[i],coins)
if numCoins + 1 < minNumCoins:
minNumCoins = numCoins + 1
return minNumCoins
2、动态规划
def changing_money(money,coins):
minNumCoins = {0:0}
for m in range(1,money+1):
if m-50-1 in minNumCoins:
del minNumCoins[m-50-1]
minNumCoins[m] = float("inf")
for i in range(len(coins)):
if m >= coins[i]:
if minNumCoins[m-coins[i]] + 1 < minNumCoins[m]:
minNumCoins[m] = minNumCoins[m-coins[i]] + 1
return minNumCoins[money]
