A Python DP solution

  • 0
    class Solution(object):
        def coinChange(self, coins, amount):
            if amount == 0: return 0
            if not coins: return -1
            maxval = 99999
            dp = [maxval for i in xrange(amount+1)]
            dp[0] = 0
            for v in xrange(1, amount+1):
                for c in coins:
                    if c <= v:
                        dp[v] = min(dp[v], 1+dp[v-c])
            if dp[amount] == maxval: return -1
            return dp[amount]

Log in to reply

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