Python
coins = (1, 2, 5, 10, 20, 50, 100, 200)
memo = {}
def first_denomination(kinds_of_coins):
return coins[kinds_of_coins - 1]
def count_change(amount, kinds_of_coins):
if (amount, kinds_of_coins) in memo:
return memo[(amount, kinds_of_coins)]
elif amount == 0:
return 1
elif amount < 0:
return 0
elif kinds_of_coins == 0:
return 0
else:
r = count_change(amount, kinds_of_coins - 1) \
+ count_change(amount - first_denomination(kinds_of_coins), kinds_of_coins)
memo[(amount, kinds_of_coins)] = r
return r
print(count_change(200, len(coins)))
