Skip to content

Instantly share code, notes, and snippets.

@falsetru
Created Jun 18, 2012
Embed
What would you like to do?
from functools import lru_cache
coins= 10,20,50,100,200,500,1000,2000,5000,10000
@lru_cache(None)
def count(amount, idx=len(coins)-1):
if amount < 0 or idx < 0: return 0
if amount == 0: return 1
return count(amount - coins[idx], idx) + count(amount, idx-1)
print(count(1000000))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment