Python DP Solution, easy to understand


  • 0
    C
    def coinChange(self, coins, amount):
       #corner cases
        if amount == 0:
            return 0
        if len(coins) == 1 and coins[0] > amount:
            return -1
        dp = [-1 for i in range(amount + 1)]
        for i in range(1, amount + 1):
        # if the value matches the coin
            if i in coins:
                dp[i] = 1
            else:
                minV = sys.maxsize
        # since the size of coins are much less than the amount, 
        # we check if for every coin there could be a solution and find the minimum of that
                for j in coins:
                    remain = i - j
        # -1 means there is no solution, so we don't need to check if dp[i] is -1
                    if remain > 0 and dp[remain] != -1:
                        minV = min(minV, dp[remain])
                if minV ==sys.maxsize:
                    dp[i] = -1
                else:
                    dp[i] = minV + 1
        return dp[-1]

Log in to reply
 

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