Python 4 lines simple DP

  • 0

    The key idea is we update dp[i] with previous best results we got. One thing to keep in mind is if the previous result dp[i-x] == -1, it can not be used to update current dp[i] hence we ignore it.

    class Solution(object):
        def coinChange(self, coins, amount):
            :type coins: List[int]
            :type amount: int
            :rtype: int
            dp = [0]
            for i in range(1, amount+1):
                dp += [min([dp[i-x]+1 for x in coins if i-x>=0 and dp[i-x]>=0] or [-1])]
            return dp[-1]

Log in to reply

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