Introduction to the Coin Change Problem
The Coin Change Problem is one of the most classic algorithmic challenges in computer science. Given a set of coin denominations and a target amount, the goal is to determine the minimum number of coins needed to make up that amount. If the amount cannot be formed by any combination of the coins, the solution should indicate that as well.
This problem appears frequently in coding interviews, competitive programming, and real-world applications such as financial systems, vending machines, and resource allocation. Mastering it not only sharpens your dynamic programming skills but also deepens your understanding of optimization techniques in general.
Why It Matters
The Coin Change Problem matters because it teaches you how to think about overlapping subproblems and optimal substructure — the two pillars of dynamic programming. Many real-world problems, such as minimizing costs, finding shortest paths, or optimizing resource usage, share the same underlying structure.
- Interview relevance: It is a staple question at companies like Google, Amazon, and Microsoft.
- Real-world utility: Used in payment systems, currency exchange, and inventory optimization.
- Algorithmic foundation: Builds intuition for more complex DP problems like Knapsack and Edit Distance.
- Performance thinking: Demonstrates the dramatic difference between exponential brute-force and polynomial DP solutions.
Understanding the Problem
Formally, you are given an integer array coins representing coin denominations and an integer amount representing the total target value. You must return the fewest number of coins needed to make up that amount. You may assume you have an infinite supply of each coin denomination.
For example, if coins = [1, 2, 5] and amount = 11, the answer is 3 because 5 + 5 + 1 = 11 uses only three coins. If coins = [2] and amount = 3, the answer is -1 because no combination of 2-cent coins can sum to 3.
Approaches to Solve It
Brute Force Recursion
The most intuitive approach is to try every possible combination of coins recursively. For each coin, you subtract its value from the amount and recurse on the remainder. While correct, this approach has exponential time complexity because it recomputes the same subproblems repeatedly.
def coin_change_brute(coins, amount):
def helper(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
min_coins = float('inf')
for coin in coins:
result = helper(remaining - coin)
if result != float('inf'):
min_coins = min(min_coins, result + 1)
return min_coins
result = helper(amount)
return result if result != float('inf') else -1
This works for tiny inputs but becomes unusable for amounts above 30 or so due to the explosion of recursive calls.
Top-Down Dynamic Programming with Memoization
To avoid recomputing subproblems, you can cache the result of each helper(remaining) call. This technique, called memoization, reduces the time complexity to O(amount * len(coins)).
def coin_change_memo(coins, amount):
memo = {}
def helper(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
if remaining in memo:
return memo[remaining]
min_coins = float('inf')
for coin in coins:
result = helper(remaining - coin)
if result != float('inf'):
min_coins = min(min_coins, result + 1)
memo[remaining] = min_coins
return min_coins
result = helper(amount)
return result if result != float('inf') else -1
This version is much faster and is often the easiest DP solution to write correctly during an interview.
Bottom-Up Dynamic Programming
The bottom-up approach builds a table from 0 to amount, where each entry dp[i] stores the minimum coins needed to make amount i. This avoids recursion entirely and is generally more memory-efficient in practice.
def coin_change_dp(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
This is the canonical solution you should memorize. It is clean, efficient, and easy to explain.
Step-by-Step Implementation Walkthrough
Let us walk through the bottom-up solution with coins = [1, 2, 5] and amount = 11.
First, initialize a list dp of size 12 (from 0 to 11) filled with infinity, except dp[0] = 0 because zero coins are needed to make amount zero.
Then iterate from i = 1 to i = 11. For each i, check every coin. If the coin value is less than or equal to i, update dp[i] with the minimum of its current value and dp[i - coin] + 1.
For example, when i = 5, you can use coin 5 directly, so dp[5] = dp[0] + 1 = 1. When i = 11, you can use coin 5 to reach dp[6], which itself is 2 (using two 2-cent coins and one 1-cent coin, or one 5-cent and one 1-cent), giving dp[11] = dp[6] + 1 = 3.
The final table looks like this:
dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
The answer is dp[11] = 3.
Tracking the Actual Coins Used
Sometimes you need to return not just the count but the actual combination of coins. You can extend the DP table with a parallel array that records which coin was chosen at each step.
def coin_change_with_combination(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
chosen = [-1] * (amount + 1)
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0 and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
chosen[i] = coin
if dp[amount] == float('inf'):
return -1, []
combination = []
current = amount
while current > 0:
combination.append(chosen[current])
current -= chosen[current]
return dp[amount], combination
count, combo = coin_change_with_combination([1, 2, 5], 11)
print("Minimum coins:", count)
print("Combination:", combo)
This outputs the minimum number of coins and one valid combination that achieves it.
Best Practices
- Choose the right approach: Use bottom-up DP for production code, top-down memoization for quick interview solutions, and brute force only for understanding.
- Handle edge cases: Always check for
amount == 0, empty coin lists, and impossible amounts. - Sort coins first: Sorting can help with early termination in some variants, though it is not strictly necessary for the basic DP solution.
- Avoid floating point infinity: Use
amount + 1as a sentinel value instead offloat('inf')to keep everything in integers and avoid type issues. - Test thoroughly: Include test cases with large amounts, single-coin lists, and amounts that cannot be formed.
- Consider greedy carefully: A greedy approach (always picking the largest coin) works for canonical coin systems like US currency but fails for arbitrary denominations such as
[1, 3, 4]with amount 6.
Here is a robust, production-ready version using an integer sentinel:
def coin_change(coins, amount):
MAX = amount + 1
dp = [MAX] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != MAX else -1
# Test cases
assert coin_change([1, 2, 5], 11) == 3
assert coin_change([2], 3) == -1
assert coin_change([1], 0) == 0
assert coin_change([1, 3, 4], 6) == 2
print("All tests passed.")
Conclusion
The Coin Change Problem is a foundational exercise that every developer should understand deeply. By progressing from brute-force recursion to memoization and finally to bottom-up dynamic programming, you gain a clear mental model of how overlapping subproblems can be solved efficiently. The bottom-up DP solution with O(amount * len(coins)) time and O(amount) space is the gold standard for this problem, and extending it to track actual coin combinations makes it practical for real-world use. Whether you are preparing for interviews or building financial software, mastering this problem equips you with techniques that transfer directly to a wide range of optimization challenges.