Classic problem, python clean DP O(MN)


  • 2
    Z
    def change(self, amount, coins):
        dp = [1] + [0] * amount
        for c in coins:
            for i in range(1, amount + 1):
                if i >= c:
                    dp[i] += dp[i - c]
        return dp[-1]
    

  • 0
    C

    @zhongyuan9817 My codes:

    class Solution(object):
        def change(self, amount, coins):
            """
            :type amount: int
            :type coins: List[int]
            :rtype: int
            """
            dp = [ 1 if i == 0 else 0 for i in range(amount+1) ]
            for coin in coins:
                for i in range(coin, amount+1):
                    dp[i] += dp[i-coin]
            return dp[-1]
                    
    

Log in to reply
 

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