Introduction

Choosing coins with the least or no change given is a classic problem in computer science and mathematics known as the "coin change problem." The goal is to find the minimum number of coins needed to make up a certain amount, or equivalently, to determine how to give change using the fewest coins possible. This article covers two fundamental approaches: the greedy algorithm and dynamic programming, with worked examples and complexity analysis.

The Coin Change Problem

Given a set of coin denominations and a target amount, find the minimum number of coins that sum to exactly that amount. If no combination works, the problem has no solution.

Greedy Algorithm

The greedy algorithm works by always choosing the largest denomination that does not exceed the remaining amount. It is fast and intuitive but only works correctly for certain denomination sets.

Example: Make 87 cents using U.S. coins (1, 5, 10, 25, 50):

1. Choose 1 x 50-cent coin. Remaining: 37 cents.
2. Choose 1 x 25-cent coin. Remaining: 12 cents.
3. Choose 1 x 10-cent coin. Remaining: 2 cents.
4. Choose 2 x 1-cent coins. Remaining: 0 cents.

Total: 5 coins.

The greedy algorithm works for U.S. coins because the denominations are designed so that the greedy choice is always optimal. However, it fails for arbitrary denomination sets. For example, with denominations [1, 3, 4] and target 6, the greedy approach picks 4 + 1 + 1 = 3 coins, but the optimal answer is 3 + 3 = 2 coins.

Dynamic Programming

Dynamic programming (DP) finds the true minimum for any set of denominations by building up solutions from smaller subproblems.

Formulation: Define $\text{dp}[c]$ as the minimum number of coins needed to make amount $c$. The recurrence is:

$$\text{dp}[c] = \min_{d \in D}(1 + \text{dp}[c - d])$$

where $D$ is the set of available denominations and $c - d \geq 0$.

Base case: $\text{dp}[0] = 0$ (zero coins needed for amount zero).

Procedure:

1. Initialize $\text{dp}[0] = 0$ and $\text{dp}[i] = \infty$ for all $i$ from 1 to the target amount.
2. For each amount from 1 to the target, try each denomination and take the minimum.
3. The answer is $\text{dp}[\text{target}]$. If it remains $\infty$, no solution exists.

Worked Example

Denominations: [1, 3, 4], target: 6.

Result: $\text{dp}[6] = 2$, achieved by using two 3-cent coins.

Implementation

1def min_coins(denominations: list[int], target: int) -> int:
2    dp = [float('inf')] * (target + 1)
3    dp[0] = 0
4
5    for amount in range(1, target + 1):
6        for coin in denominations:
7            if coin <= amount and dp[amount - coin] + 1 < dp[amount]:
8                dp[amount] = dp[amount - coin] + 1
9
10    return dp[target] if dp[target] != float('inf') else -1
11
12
13print(min_coins([1, 3, 4], 6))   # 2
14print(min_coins([1, 5, 10, 25], 87))  # 6

Comparison Table

Variations

Counting All Combinations

Instead of finding the minimum number of coins, you may need to count how many distinct ways exist to make the target amount. The recurrence changes to a sum instead of a minimum:

$$\text{ways}[c] = \sum_{d \in D} \text{ways}[c - d]$$

Tracking Which Coins Were Used

To reconstruct the actual coin selection (not just the count), maintain a separate array that records which denomination was used at each step. Then trace back from $\text{dp}[\text{target}]$ to build the list.

Common Pitfalls

• Assuming the greedy algorithm always works. It fails for denominations like [1, 3, 4] and can even fail for [1, 15, 25] with target 30 (greedy gives 25+1+1+1+1+1 = 6 coins, optimal is 15+15 = 2 coins).
• Forgetting to handle the "no solution" case when $\text{dp}[\text{target}]$ remains infinity.
• Using signed integer types without checking for overflow when initializing with a large sentinel value.

Conclusion

The coin change problem is a fundamental exercise in algorithmic thinking. The greedy approach is fast and works for well-designed currency systems, but dynamic programming provides a guaranteed-optimal solution for any set of denominations. Understanding both approaches, and knowing when greedy fails, is essential for algorithm design and technical interviews.