A/C Python solution, easy to understand, DP, beat 0.55%


  • 0
    W
    def coinChange(self, coins, amount):
        coins = sorted(coins)
        #print "coins = ", coins, " amount = ", amount
    
        d = {}
        d[0] = 0
        for coin in coins:
            d[coin] = 1
    
    
        minCoin = coins[0]
        #print "minCoin = ", minCoin
    
        if amount == 0:
            return 0
        
        elif minCoin > amount:
            return -1
    
        for i in range(1, minCoin):
            #print "i = ", i
            d[i] = float('inf')
    
        def helper(n):
            #print "helper n = ", n
    
            if n in d:
                #print "d[n] = ", d[n]
                return d[n]
            else:
                iniVal = float('inf')
                for coin in coins:
                    #print "coin = ", coin
    
                    if n >= coin:
                        tmp = helper(n-coin) + helper(coin)
                    else:
                        tmp = float('inf')
    
                    if tmp < iniVal:
                        iniVal = tmp
    
                #print "iniVal = ", iniVal
    
    
                d[n] = iniVal
    
                return d[n]
    
        res = helper(amount)
    
        #print "d = ", d
        #print "res = ", res
    
        if res == float('inf'):
            return -1
        else:
            return res

Log in to reply
 

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