Python solution with detailed explanation


  • 0
    G

    Solution

    Coin Change https://leetcode.com/problems/coin-change/?tab=Description

    Memoization

    • Sketch a recursion tree and add a cache to store intermediate results.
    class Solution(object):
        def helper(self, coins, amount, cache):
            if amount == 0:
                return 0
            elif amount in cache:
                return cache[amount]
            cache[amount] = float('inf')
            for c in coins:
                if amount - c >= 0:
                    cache[amount] = min(cache[amount], self.helper(coins, amount-c, cache) + 1)
            return cache[amount]
        
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            if amount == 0:
                return 0
            elif min(coins) > amount:
                return -1
            else:
                coins.sort(reverse=True)
                answer = self.helper(coins, amount, {})
                return answer if answer != float('inf') else -1
    

    Dynamic Programming

    class Solution(object):
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            MAX = amount + 1
            coins.sort(reverse=True)
            dp = [MAX]*(MAX)
            dp[0] = 0
            for i in xrange(1, MAX):
                dp[i] = min([dp[i-c] if i>=c else (MAX) for c in coins]) ### List Comprehension is faster
                dp[i] = dp[i] + 1 if dp[i] != MAX else dp[i]
            return -1 if (dp[-1] == MAX) else dp[-1]
    

    Breadth First Search


Log in to reply
 

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