You are viewing a single comment's thread. Return to all comments →
Works for arbitrary number of coins with arbitrary values. Standard dp, use memoization or @cache python builtin.
def solve(n, coins, v=[1, 2, 5, 10]): @cache def dp(s, p): if s==0 or p==0: return 1 if s<=coins[p] else 0 return sum(dp(s-i*v[p], p-1) for i in range(min(coins[p], s//v[p])+1)) return dp(n, len(coins))
Seems like cookies are disabled on this browser, please enable them to open this website
Coinage
You are viewing a single comment's thread. Return to all comments →
5 line Python, 100%
Works for arbitrary number of coins with arbitrary values. Standard dp, use memoization or @cache python builtin.