Two short Pythons


  • 5

    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

  • 0
    A

    Thanks, especially for list comprehension optimization. :)


  • 0
    D

    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.


Log in to reply
 

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