LC-0322 Medium LeetCode

322. Coin Change

Array Dynamic Programming Breadth-First Search

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 46% Topics: Array, Dynamic Programming, Breadth-First Search

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(n * k), n is the number of coins, k is the amount of money
# Space: O(k)

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        INF = 0x7fffffff  # Using float("inf") would be slower.
        dp = [INF] * (amount + 1)
        dp[0] = 0
        for i in xrange(amount + 1):
            if dp[i] != INF:
                for coin in coins:
                    if i + coin <= amount:
                        dp[i + coin] = min(dp[i + coin], dp[i] + 1)
        return dp[amount] if dp[amount] != INF else -1

Solution from kamyu104/LeetCode-Solutions · MIT