Two short Pythons

• Dynamic programming with `need[a]` telling the number of coins needed for amount `a`. "Not (yet) possible" is represented by `amount + 1`, since the worst actually possible solution is `amount` coins (each having value 1).

Solution 1 ... about 940ms, best 916ms

``````def coinChange(self, coins, amount):
need = [0] + [amount + 1] * amount
for a in xrange(min(coins), amount + 1):
need[a] = min([need[a - c] for c in coins if c <= a]) + 1
return need[-1] if need[-1] <= amount else -1
``````

I prefer `min( ... )` over `min([ ... ])`, but generators tend to be slower than list comprehensions, and here I wanted fast.

Starting `a` at `min(coins)` is a little optimization and more importantly prevents `min` from getting nothing and erroring on me (I know, I know... it would still fail if there were an input with no coins... if there were, I'd probably prefix the loop with `if coins:`).

Solution 2 ... about 1520ms, best 1460ms

``````def coinChange(self, coins, amount):
need = [0] + [amount + 1] * amount
for c in coins:
for a in xrange(c, amount+1):
need[a] = min(need[a], need[a - c] + 1)
return need[-1] if need[-1] <= amount else -1``````

• Thanks, especially for list comprehension optimization. :)

• Great answer. I had pretty much the same solution, but without the optimizations and it wasn't accepted =/. I guess that's what the solutions are looking for.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.