Coin Change
Problem
Given an integer array coins representing coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. If the amount cannot be made up by any combination of the coins, return -1.
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 2³¹ - 1
- 0 ≤ amount ≤ 10⁴
Example
coins = [1, 2, 5], amount = 113The brute-force approach tries all combinations of coins to sum to 11, which is exponential and inefficient. The optimal solution uses recursion with memoization to avoid redundant calculations. For example, to compute dp(11), the algorithm tries dp(10), dp(9), and dp(6) by subtracting coins 1, 2, and 5 respectively. Each subproblem is solved once and cached. The critical moment is when dp(6) is computed, which itself depends on smaller amounts. By caching results, the algorithm avoids recomputing dp(6) multiple times, drastically reducing the total work. The final answer is dp(11) = 3, corresponding to coins [5,5,1].
Approach
Straightforward Solution
A brute-force recursive approach tries all combinations of coins to sum to the amount, leading to exponential time complexity because it recomputes the same subproblems multiple times.
Core Observation
The minimum number of coins needed for amount A depends on the minimum number needed for smaller amounts A - coin, for each coin denomination. This recursive dependency forms overlapping subproblems with optimal substructure, making Dynamic Programming the natural fit.
Path to Optimal
Recognizing overlapping subproblems, memoization caches results of dp(rem) calls to avoid redundant work. The problem is reframed as: for each amount rem, find the minimum among dp(rem - coin) + 1 for all coins. This top-down DP with memoization reduces the complexity from exponential to polynomial.
Optimal Approach
Implement a recursive function dp(rem) that returns the minimum coins needed for rem. Base cases handle rem < 0 (impossible) and rem == 0 (zero coins). For each coin, recursively compute dp(rem - coin), and take the minimum result plus one. Memoize results to ensure each subproblem is solved once. Finally, return dp(amount) or -1 if no solution exists.
Time
O(amount * n)
Each amount from 0 to amount is computed at most once, and for each amount, the algorithm iterates over all n coin denominations, resulting in O(amount * n) time.
Space
O(amount)
The memoization dictionary stores results for each amount up to the target, requiring O(amount) auxiliary space. The recursion stack depth is at most amount, which is also O(amount).
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When a problem involves finding an optimal value over overlapping subproblems with recursive dependencies, use memoization to cache results and avoid exponential recomputation, transforming brute-force recursion into efficient DP.
Solution
| 1 | class Solution:
|
| 2 | def coinChange(self, coins: list[int], amount: int) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(rem):
|
| 6 | if rem < 0:
|
| 7 | return float('inf')
|
| 8 | if rem == 0:
|
| 9 | return 0
|
| 10 | if rem in memo:
|
| 11 | return memo[rem]
|
| 12 |
|
| 13 | min_coins = float('inf')
|
| 14 | for coin in coins:
|
| 15 | res = dp(rem - coin)
|
| 16 | if res != float('inf'):
|
| 17 | min_coins = min(min_coins, res + 1)
|
| 18 |
|
| 19 | memo[rem] = min_coins
|
| 20 | return min_coins
|
| 21 |
|
| 22 | result = dp(amount)
|
| 23 | return result if result != float('inf') else -1 |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int coinChange(int[] coins, int amount) { |
| 6 | Map<Integer, Integer> memo = new HashMap<>(); |
| 7 | |
| 8 | return dp(amount, coins, memo); |
| 9 | } |
| 10 | |
| 11 | private int dp(int rem, int[] coins, Map<Integer, Integer> memo) { |
| 12 | if (rem < 0) { |
| 13 | return Integer.MAX_VALUE; |
| 14 | } |
| 15 | if (rem == 0) { |
| 16 | return 0; |
| 17 | } |
| 18 | if (memo.containsKey(rem)) { |
| 19 | return memo.get(rem); |
| 20 | } |
| 21 | |
| 22 | int minCoins = Integer.MAX_VALUE; |
| 23 | for (int coin : coins) { |
| 24 | int res = dp(rem - coin, coins, memo); |
| 25 | if (res != Integer.MAX_VALUE) { |
| 26 | minCoins = Math.min(minCoins, res + 1); |
| 27 | } |
| 28 | } |
| 29 | |
| 30 | memo.put(rem, minCoins); |
| 31 | return minCoins; |
| 32 | } |
| 33 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | #include <algorithm> |
| 4 | #include <climits> |
| 5 | |
| 6 | using namespace std; |
| 7 | |
| 8 | class Solution { |
| 9 | public: |
| 10 | int coinChange(vector<int>& coins, int amount) { |
| 11 | unordered_map<int, int> memo; |
| 12 | return dp(amount, coins, memo); |
| 13 | } |
| 14 | |
| 15 | private: |
| 16 | int dp(int rem, vector<int>& coins, unordered_map<int, int>& memo) { |
| 17 | if (rem < 0) { |
| 18 | return INT_MAX; |
| 19 | } |
| 20 | if (rem == 0) { |
| 21 | return 0; |
| 22 | } |
| 23 | if (memo.find(rem) != memo.end()) { |
| 24 | return memo[rem]; |
| 25 | } |
| 26 | |
| 27 | int minCoins = INT_MAX; |
| 28 | for (int coin : coins) { |
| 29 | int res = dp(rem - coin, coins, memo); |
| 30 | if (res != INT_MAX) { |
| 31 | minCoins = min(minCoins, res + 1); |
| 32 | } |
| 33 | } |
| 34 | |
| 35 | memo[rem] = minCoins; |
| 36 | return minCoins; |
| 37 | } |
| 38 | }; |
| 1 | var coinChange = function(coins, amount) { |
| 2 | const memo = new Map(); |
| 3 | |
| 4 | function dp(rem) { |
| 5 | if (rem < 0) { |
| 6 | return Infinity; |
| 7 | } |
| 8 | if (rem === 0) { |
| 9 | return 0; |
| 10 | } |
| 11 | if (memo.has(rem)) { |
| 12 | return memo.get(rem); |
| 13 | } |
| 14 | |
| 15 | let minCoins = Infinity; |
| 16 | for (const coin of coins) { |
| 17 | const res = dp(rem - coin); |
| 18 | if (res !== Infinity) { |
| 19 | minCoins = Math.min(minCoins, res + 1); |
| 20 | } |
| 21 | } |
| 22 | |
| 23 | memo.set(rem, minCoins); |
| 24 | return minCoins; |
| 25 | } |
| 26 | |
| 27 | const result = dp(amount); |
| 28 | return result === Infinity ? -1 : result; |
| 29 | }; |
Step-by-Step Solution
Initialize Memoization Cache and Define Recursive DP Function
| 3 | memo = {}
|
| 5 | def dp(rem):
|
| 6 | if rem < 0:
|
| 7 | return float('inf')
|
| 8 | if rem == 0:
|
| 9 | return 0
|
| 10 | if rem in memo:
|
| 11 | return memo[rem]
|
Objective
To set up a cache for storing computed results and define the recursive function that computes the minimum coins for a given remainder.
Key Insight
Memoization is essential to avoid recomputing the minimum coins for the same remainder multiple times. Defining the recursive dp(rem) function encapsulates the problem of finding the minimum coins for any sub-amount rem, enabling a clean top-down DP approach.
Interview Quick-Check
Core Logic
Memoization cache stores results for each remainder to ensure each subproblem is solved once.
State & Boundaries
The dp function handles base cases for rem < 0 (impossible) and rem == 0 (zero coins).
Common Pitfalls & Bugs
Forgetting to check the memo before recursion leads to exponential time complexity.
Compute Minimum Coins by Exploring All Coin Choices
| 13 | min_coins = float('inf')
|
| 14 | for coin in coins:
|
| 15 | res = dp(rem - coin)
|
| 16 | if res != float('inf'):
|
| 17 | min_coins = min(min_coins, res + 1)
|
Objective
To recursively compute the minimum coins needed for the current remainder by trying all coin denominations and selecting the best option.
Key Insight
For each coin, the algorithm recursively computes the minimum coins needed for rem - coin. If that subproblem is solvable, it updates the minimum coins for rem by considering one additional coin. This exhaustive exploration ensures the global minimum is found by combining optimal sub-results.
Interview Quick-Check
Core Logic
The dp function tries all coins, recursively computing dp(rem - coin), and takes the minimum among these plus one coin.
State & Boundaries
Only consider subproblems that are solvable (dp(rem - coin) != infinity).
Common Pitfalls & Bugs
Failing to handle the case where no coin fits leads to incorrect results or infinite recursion.
Cache Computed Result and Return Final Answer
| 19 | memo[rem] = min_coins
|
| 20 | return min_coins
|
| 22 | result = dp(amount)
|
| 23 | return result if result != float('inf') else -1 |
Objective
To store the computed minimum coins for the current remainder in the memo and return the final result for the original amount.
Key Insight
Caching the result for each remainder ensures that future calls with the same remainder return instantly, preventing redundant work. The final return statement converts an infinite result to -1, signaling no solution exists, which aligns with the problem requirements.
Interview Quick-Check
Core Logic
Memoizing the minimum coins for each remainder guarantees each subproblem is solved once.
State & Boundaries
Return -1 if the final result is infinity, indicating no valid coin combination.
Common Pitfalls & Bugs
Forgetting to memoize results or incorrectly handling the no-solution case leads to incorrect answers or inefficiency.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
memo = {}Initialize a dictionary to memoize results for subproblems.
This cache is critical to store the minimum coins needed for each remainder, preventing redundant recursive calls and reducing exponential complexity to polynomial.
def dp(rem):Define the recursive function dp that computes minimum coins for remainder rem.
Encapsulating the problem as dp(rem) allows a clean top-down dynamic programming approach that naturally expresses the problem's optimal substructure.
return float('inf')Return infinity to mark this branch as impossible after overshooting the target amount.
If rem < 0, no sequence of positive coins can bring the remainder back to 0, so this path must never be chosen in the minimum.
if rem == 0:Check whether the remainder is exactly zero (the success base case).
When rem == 0, the target has been formed exactly, so recursion should stop and return 0 coins needed (handled on the next line).
if rem < 0:Return infinity if remainder is negative, indicating no solution.
This base case prevents invalid paths from contributing to the solution, effectively pruning impossible branches.
return 0Return 0 if remainder is zero, meaning no more coins are needed.
This base case anchors the recursion, signaling that the exact amount has been formed with zero additional coins.
if rem in memo:Check if the result for remainder rem is already computed in memo.
This lookup is the essence of memoization, enabling O(1) retrieval of previously solved subproblems and avoiding recomputation.
return memo[rem]Return the cached result if available.
Returning cached results immediately prunes the recursion tree, ensuring polynomial time complexity.
min_coins = float('inf')Initialize min_coins to infinity to track the minimum coins needed.
Starting with infinity ensures any valid solution found will replace this initial value, correctly identifying the minimum.
for coin in coins:Iterate over each coin denomination to explore choices.
Trying all coins ensures the algorithm considers every possible way to form the remainder, guaranteeing the global minimum is found.
res = dp(rem - coin)Recursively compute minimum coins needed for rem minus current coin.
This recursive call breaks down the problem into smaller subproblems, leveraging optimal substructure.
if res != float('inf'):Check if the subproblem result is valid (not infinity).
Ignoring invalid subproblems prevents incorrect updates and infinite recursion.
min_coins = min(min_coins, res + 1)Update min_coins with the minimum between current and new candidate.
This line embodies the core DP recurrence, selecting the best among all coin choices to minimize coin count.
memo[rem] = min_coinsStore the computed minimum coins for remainder rem in memo.
Memoization here is crucial to ensure each subproblem is solved once, enabling efficient reuse of results.
return min_coinsReturn the memoized minimum coins for remainder rem.
Returning the cached result completes the recursive call, propagating the optimal solution upward.
result = dp(amount)Call dp with the original amount to compute the final answer.
This initiates the top-down DP process, triggering recursive exploration and memoization.
return result if result != float('inf') else -1Return the result if valid, otherwise return -1 indicating no solution.
Converting infinity to -1 aligns with problem requirements, signaling that the amount cannot be formed with given coins.
Test Your Understanding
Why is memoization critical in this recursive solution for coin change?
Memoization prevents redundant computations of the same subproblems by caching results, reducing the exponential brute-force recursion to polynomial time.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Coin Change from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Coin Change drill