Skip to content

322. Coin Change

Summary

Solution Approach Explanation (1-minute) Time Complexity Space Complexity
Dynamic Programming (Bottom-up) Build solution from amount 0 to target amount. For each amount, try all coins and take minimum coins needed. Use dp[i] to store minimum coins for amount i. O(amount × coins) O(amount)

Implementation

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1] * (amount+1)
        dp[0] = 0
        for a in range(1, amount+1):
            for c in coins:
                if a >= c:
                    dp[a] = min(
                        dp[a],
                        dp[a-c] + 1
                    )

        if dp[amount] == amount+1:
            return -1
        else:
            return dp[amount]