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
```