The Coin Change Problem is one of the most classic and important problems in Dynamic Programming. It is widely used in coding interviews, competitive programming, and algorithm design. The challenge is to determine the minimum number of coins needed to make up a certain amount using given coin denominations.
This article will cover the Coin Change Problem (Minimum Coins Version) in detail. We will explore the problem statement, recursive and dynamic programming approaches, complexity analysis, and real-world applications. You’ll also find practical Python implementations, examples with outputs, and visualization using mermaid diagrams to ensure complete clarity.
Problem Statement
Given a set of coins with denominations coins[] and a target amount amount, find the minimum number of coins needed to make up the amount. If it is not possible, return -1.
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1 (3 coins)
Input: coins = [2], amount = 3
Output: -1
Explanation: Impossible to make 3 using only coin 2
Naive Recursive Approach
A brute-force idea is to try every possible coin and recursively reduce the amount until reaching zero. However, this approach leads to exponential complexity because it recalculates overlapping subproblems.
As shown, the tree overlaps many subproblems (like making 6 in multiple branches). This redundancy makes recursion inefficient.
Dynamic Programming Approach
Dynamic Programming optimizes recursion by storing results of subproblems. We use a bottom-up DP table where dp[i] represents the minimum number of coins needed to make amount i.
Recurrence Relation:
dp[i] = min( dp[i - coin] + 1 ) for each coin in coins[] if (i - coin) ≥ 0
Base Case:
dp[0] = 0 — zero coins are needed to make up amount 0.
Python Implementation
def coin_change(coins, amount):
# Initialize DP table with a large value (infinity)
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case
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
# Example Test Cases
print(coin_change([1, 2, 5], 11)) # Output: 3
print(coin_change([2], 3)) # Output: -1
print(coin_change([1], 0)) # Output: 0
Output:
3
-1
0
Step-by-Step Example
Let us solve coins = [1, 3, 4], amount = 6 step by step:
For amount 6, the optimal change is 2 coins: {3, 3}. The DP solution avoids recomputation and efficiently builds up the answer.
Time and Space Complexity
- Time Complexity: O(N * amount) where N is the number of coin denominations.
- Space Complexity: O(amount) for the DP array. This can be optimized further if only partial storage is required.
When to Use Coin Change DP
- When computing minimum coins in financial software systems.
- Optimizing exchange machines (ATMs, vending machines).
- As a subproblem in other resource allocation and optimization problems.
- Competitive programming problems requiring coin selection strategies.
Interactive Visualization (Try It Yourself)
Here’s a simple way to interact with the DP concept using Python. Copy and run this snippet to visualize table values at each step:
def visualize_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)
print(f"dp[{i}] = {dp[i] if dp[i] != float('inf') else '∞'}")
return dp[amount] if dp[amount] != float('inf') else -1
visualize_dp([1, 3, 4], 6)
Output Trace:
dp[1] = 1
dp[2] = 2
dp[3] = 1
dp[4] = 1
dp[5] = 2
dp[6] = 2 ✅ Optimal Answer
Conclusion
The Coin Change Problem (Minimum Coins) provides an excellent introduction to Dynamic Programming concepts like overlapping subproblems and optimal substructure. By building solutions from the bottom up, we efficiently compute the minimum number of coins required. This method is not only optimal but also extends its power to related optimization problems in computer science, finance, and system design.
With theory, examples, mermaid diagrams, and Python code, you now have everything needed to master this classic problem.
