Skip to content

Instantly share code, notes, and snippets.

@shawnchin

shawnchin/coin_change.py

Created September 1, 2017 07:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save shawnchin/2044a2a08a095ade060ffeecc8729eff to your computer and use it in GitHub Desktop.
Save shawnchin/2044a2a08a095ade060ffeecc8729eff to your computer and use it in GitHub Desktop.
Download ZIP
Raw
coin_change.py
# https://www.hackerrank.com/challenges/coin-change/problem
def cc_dp(target, coins):
current = [0] * (target + 1)
current[0] = 1
prev = current[:]
for c in coins:
for t in xrange(target + 1):
current[t] = prev[t] + sum(prev[rem] for rem in xrange(t - c, -1, -c))
prev, current = current, prev
return prev[-1]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment