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 =  + [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
min( ... ) over
min([ ... ]), but generators tend to be slower than list comprehensions, and here I wanted fast.
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
Solution 2 ... about 1520ms, best 1460ms
def coinChange(self, coins, amount): need =  + [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