Introduction

The coin change problem is a classic algorithm exercise: given a set of coin denominations and a target amount, determine the minimum number of coins needed to make that amount. It shows up in dynamic programming because a greedy choice is not always optimal.

The problem is small enough to explain clearly, but rich enough to teach several important ideas about optimal substructure and state transitions.

Why Greedy Is Not Always Correct

A greedy strategy always takes the largest available coin first. That works for some coin systems, but not for all of them.

For example, with coins [1, 3, 4] and amount 6, a greedy algorithm picks 4, then 1, then 1, using three coins. The optimal solution is 3 + 3, which uses only two coins.

That is why the general solution is usually dynamic programming rather than greedy selection.

Dynamic Programming For Minimum Coins

The standard DP idea is to compute the best answer for every amount from 0 up to the target. Let dp[a] be the minimum number of coins needed to make amount a.

The recurrence is:

• 'dp[0] = 0'
• for every amount a, try each coin c
• if a - c is reachable, then dp[a] can be updated from dp[a - c] + 1

A simple Python implementation looks like this:

1def min_coins(coins, amount):
2    dp = [float("inf")] * (amount + 1)
3    dp[0] = 0
4
5    for a in range(1, amount + 1):
6        for coin in coins:
7            if coin <= a:
8                dp[a] = min(dp[a], dp[a - coin] + 1)
9
10    return dp[amount] if dp[amount] != float("inf") else -1
11
12
13print(min_coins([1, 3, 4], 6))
14print(min_coins([2], 3))

The first call returns 2. The second returns -1, which indicates that the amount cannot be formed from the given denominations.

Reconstructing Which Coins Were Used

Sometimes you need the actual coin combination, not just the count. You can store the last coin chosen for each amount and reconstruct the path afterward:

1def min_coins_with_solution(coins, amount):
2    dp = [float("inf")] * (amount + 1)
3    prev = [-1] * (amount + 1)
4    dp[0] = 0
5
6    for a in range(1, amount + 1):
7        for coin in coins:
8            if coin <= a and dp[a - coin] + 1 < dp[a]:
9                dp[a] = dp[a - coin] + 1
10                prev[a] = coin
11
12    if dp[amount] == float("inf"):
13        return -1, []
14
15    result = []
16    current = amount
17    while current > 0:
18        coin = prev[current]
19        result.append(coin)
20        current -= coin
21
22    return dp[amount], result
23
24
25print(min_coins_with_solution([1, 3, 4], 6))

This version returns both the minimum count and one optimal set of coins.

Time Complexity

If there are m coin denominations and the target amount is n, the standard DP solution runs in O(m * n) time and uses O(n) space.

That is efficient enough for many practical input sizes, especially compared with naive recursion that recomputes the same subproblems repeatedly.

Common Pitfalls

The biggest mistake is assuming the greedy algorithm always works. It does for some coin systems, but not for the general problem.

Another pitfall is forgetting to handle unreachable amounts. If no combination of coins can form the target, the algorithm should return a clear failure value instead of pretending a solution exists.

A third issue is confusing two different problems: minimizing the number of coins and counting the number of ways to make the amount. Those are related but distinct dynamic programming problems with different recurrences.

Summary

• The general coin change problem is usually solved with dynamic programming.
• Greedy selection is not always optimal.
• 'dp[a] stores the minimum coins needed for amount a.'
• You can store predecessor information to reconstruct the chosen coins.
• The standard minimum-coin DP runs in O(m * n) time and O(n) space.