NUHMAN.com

Introduction

LeetCode 322: Coin Change is a classic dynamic programming problem. It asks us to determine the minimum number of coins needed to make a certain amount using coins of given denominations. This problem tests our ability to decompose problems using subproblems and optimal solutions.

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example

python

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Input: coins = [2], amount = 3
Output: -1

Input: coins = [1], amount = 0
Output: 0

Step-by-Step Solution

🧠 Intuition

We need to find the minimum number of coins that sum up to a given amount. Since we can use coins infinitely, this resembles an unbounded knapsack problem.

We will use bottom-up dynamic programming, building a solution from amount = 0 to amount = target.

✅ Approach: Bottom-Up Dynamic Programming

1. DP Array:
2. Create a dp array of size amount + 1 where dp[i] represents the minimum number of coins needed to make amount i.
3. Initialization:
4. Initialize dp[0] = 0 (zero coins are needed to make amount 0). For all other amounts, initialize with a large value like float('inf').
5. Transition Formula:
6. For each coin and for each sub-amount from coin to amount, update:

python

dp[i] = min(dp[i], dp[i - coin] + 1)

1. Final Answer:
2. If dp[amount] is still inf, return -1. Otherwise, return dp[amount].

✅ Python Code

python

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        # Initialize dp array with "infinity" except dp[0]
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        # Fill dp array
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)

        return dp[amount] if dp[amount] != float('inf') else -1

🧪 Dry Run Example

For coins = [1, 2, 5] and amount = 11, the dp array gets filled as:

text

dp[0] = 0
dp[1] = 1  (1)
dp[2] = 1  (2)
dp[3] = 2  (2+1)
dp[4] = 2  (2+2)
dp[5] = 1  (5)
dp[6] = 2  (5+1)
dp[7] = 2  (5+2)
dp[8] = 3  (5+2+1)
dp[9] = 3  (5+2+2)
dp[10] = 2 (5+5)
dp[11] = 3 (5+5+1)

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(amount × len(coins))Space ComplexityO(amount)

🔍 Edge Cases

1. amount = 0 → return 0
2. coins = [2], amount = 3 → return -1 (no combination possible)
3. coins = [1], large amount → should return amount

✅ Alternative Approach: Top-Down with Memoization

python

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        from functools import lru_cache
        
        @lru_cache(None)
        def dp(rem):
            if rem < 0: return float('inf')
            if rem == 0: return 0
            return min(dp(rem - coin) + 1 for coin in coins)

        res = dp(amount)
        return res if res != float('inf') else -1

🧠 Key Insight

The key idea is to reuse solutions to subproblems. For each amount, we store the minimum coins required to get there and build from the bottom up. Avoid recomputation through memoization (top-down) or iteration (bottom-up).

✅ Conclusion

LeetCode 322: Coin Change is a classic dynamic programming problem that teaches subproblem reuse and state transition modeling. Understanding this problem lays a solid foundation for tackling similar unbounded knapsack or resource minimization problems.