Simple DP in Python


  • 0
    Y
    class Solution(object):
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            if(amount == 0):
                return 0
                
            total = [-1] * amount
            for x in range(amount):
                if x + 1 in coins:
                    total[x] = 1
                else:
                    all = [total[x-c] for c in coins if x>=c and total[x-c] != -1]
                    if(len(all) > 0):
                        total[x] = min(all) + 1
                        
            return total[-1]

Log in to reply
 

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