Python DP Solution -- Coin Change

  • 7
    class Solution(object):
        def coinChange(self, coins, amount):
            :type coins: List[int]
            :type amount: int
            :rtype: int
            rs = [amount+1] * (amount+1)
            rs[0] = 0
            for i in xrange(1, amount+1):
                for c in coins:
                    if i >= c:
                        rs[i] = min(rs[i], rs[i-c] + 1)
            if rs[amount] == amount+1:
                return -1
            return rs[amount]

Log in to reply

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