Coin Change Explained: Min Coins for Amount 6 with [1, 3, 4]
Master the Coin Change DP problem by tracing amount 6 with coins [1, 3, 4]. Learn why greedy fails, build mental models, and handle edge cases like -1.
By Learnisim AI·Published October 4, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
Min coins for amount 6 with coins [1, 3, 4] overview diagram
Why
Why Greedy Fails: Making Change with Coins [1, 3, 4]
Phase 1: The Trap of the Largest Coin
Imagine you are at a cash register with an unlimited supply of coins in denominations coins=[1,3,4], and your target amount is 6. Your goal is simple: find the absolute fewest number of coins needed to sum up to 6.
Your first instinct is likely the greedy approach—grab the largest coin possible that doesn't overshoot the target, then repeat. For our setup, you take a 4, leaving you with 2 remaining. Since a 4 is now too big, you drop down to the next largest coin that fits, which is a 1, leaving 1. You grab one more 1, and you are done.
Greedy choice: 4+1+1=3 coins
It feels logical, fast, and efficient. But step back and check if it is truly optimal. What if instead you picked two 3s?
Optimal choice: 3+3=2 coins
Your greedy shortcut used 3 coins, but the actual minimum is just 2 coins. This failure mode proves that picking locally optimal pieces does not guarantee a globally minimum result, forcing us to explore a systematic way to check all overlapping subproblems.
Why Greedy Fails: Making Change with Coins [1, 3, 4] diagram
Model
Defining DP State and Transitions for Minimum Coins
Phase 2: The Staircase of Subproblems
When greedy algorithms fail—like taking 4 first and getting stuck with 4+1+1 (three coins) instead of the optimal 3+3 (two coins)—we need a strategy that evaluates all paths without guessing. We transition from a local heuristic to a global search space by asking a simpler question: What is the minimum coin count to make every sub-amount from 0 up to our target 6?
We define an array dp where dp[x] represents the minimum number of coins needed to make amount x. To fill this array, we build up from the base case of amount 0, which requires 0 coins (dp[0]=0). For any other amount x, if we decide to use a particular coin c, the remaining amount we must make is x−c.
This gives us our core recurrence relation:
dp[x]=min(dp[x],dp[x−c]+1)
For our working example where coins=[1,3,4] and amount=6, we can visualize each cell in our dp array as a step on a staircase. To reach step 6, we look backward by the size of each available coin (1, 3, and 4), inspect the minimum coins required at those previous steps, and add 1 (for the coin we just picked).
dp[x]=min(dp[x],dp[x−coin]+1)
Defining DP State and Transitions for Minimum Coins diagram
Worked example
Tracing Coin Change for Amount 6 with Coins [1, 3, 4]
Phase 3: Working Through the DP Table
Let us trace our locked example: finding the minimum coins to make amount 6 using the coin set [1, 3, 4]. We will maintain an array dp of size 7 (indices 0 to 6), where dp[x] stores the minimum coins needed to make amount x.
Given
- coins = [1, 3, 4] - amount = 6 - Initial state: dp[0] = 0, and all other indices dp[1] through dp[6] initialized to ∞ (or a sentinel value like 7).
Steps
We iterate through each coin and update all reachable amounts from coin up to amount using the transition:
dp[x]=min(dp[x],dp[x−coin]+1)
1. Processing coin 1: - x = 1: min(∞,dp[0]+1)=1impliesdp[1]=1 - x = 2: min(∞,dp[1]+1)=2impliesdp[2]=2 - x = 3: min(∞,dp[2]+1)=3impliesdp[3]=3 - x = 4: min(∞,dp[3]+1)=4impliesdp[4]=4 - x = 5: min(∞,dp[4]+1)=5impliesdp[5]=5 - x = 6: min(∞,dp[5]+1)=6impliesdp[6]=6 - Table after coin 1:[0, 1, 2, 3, 4, 5, 6]
2. Processing coin 3: - x = 3: min(3,dp[0]+1)=1impliesdp[3]=1 - x = 4: min(4,dp[1]+1)=2impliesdp[4]=2 - x = 5: min(5,dp[2]+1)=3impliesdp[5]=3 - x = 6: min(6,dp[3]+1)=2impliesdp[6]=2 - Table after coin 3:[0, 1, 2, 1, 2, 3, 2]
3. Processing coin 4: - x = 4: min(2,dp[0]+1)=1impliesdp[4]=1 - x = 5: min(3,dp[1]+1)=2impliesdp[5]=2 - x = 6: min(2,dp[2]+1)=3 (stays 2, since min(2,3)=2) - Final table:[0, 1, 2, 1, 1, 2, 2]
Result
The final value at dp[6] is 2. This corresponds to using two 3-value coins (3+3=6), successfully bypassing the suboptimal greedy choice of 4+1+1 (3 coins).
Tracing Coin Change for Amount 6 with Coins [1, 3, 4] diagram
Practice
Predicting DP Table States for a Custom Coin Denomination
Phase 4: Practice Your Transition Logic
Now that you have seen how the bottom-up dynamic programming table updates for amount 6 using coins = [1, 3, 4], it is time to test your mental model on a slightly different variation of the same system. Instead of target amount 6, let us shrink the target to 4 using the exact same coin denominations: coins = [1, 3, 4].
Before jumping to the full table, trace out what happens as you evaluate each coin for target amounts 1 through 4. Remember the recurrence relation from the previous phase:
dp[x]=min(dp[x],dp[x−coin]+1)
Think about how dp[4] is formed directly by taking a single coin of value 4, compared to building it up from smaller sub-amounts like dp[3] + 1 or dp[1] + 3.
python
coins = [1, 3, 4]
amount = 4
# Predict the final value of dp[4] and the number of coins required.
# What intermediate values are stored in dp[0], dp[1], dp[2], dp[3], and dp[4]?
Apply
Applying the Min Coins DP Pattern to a New Target
Phase 5: Transfer
We have solved the locked example for amount 6 using coins [1,3,4], finding that the optimal solution requires 2 coins (3+3), avoiding the greedy trap of 4+1+1. The fundamental recurrence relation dp[x]=min(dp[x],dp[x−c]+1) and base case dp[0]=0 apply to any combination of coin denominations and target amounts.
To test this transfer of knowledge, consider how the table behaves if we alter the target amount or the coin set while keeping the exact same bottom-up execution structure. Recognizing when a problem maps directly to this unbounded knapsack-style recurrence allows you to bypass redundant search trees and solve optimization tasks efficiently in O(amount×coins) time.
python
def coinChangeTransfer(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for x in range(1, amount + 1):
for c in coins:
if x - c >= 0:
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
FAQ
Why does the greedy approach fail for the coin change problem with coins [1, 3, 4] and amount 6?
A greedy approach always picks the largest possible coin first. For amount 6 with [1, 3, 4], greedy picks 4 first, leaving amount 2, which requires two 1s (4 + 1 + 1 = 3 coins). However, the optimal solution is 3 + 3 = 2 coins. Dynamic programming evaluates all choices to avoid this trap.
What does the DP state dp[i] represent in the coin change problem?
dp[i] represents the minimum number of coins needed to make up the target amount i using the given coin denominations.
What is the time and space complexity of the coin change DP solution?
The time complexity is O(amount * n), where n is the number of coin denominations, because we compute the value for every amount from 1 to the target using each coin. The space complexity is O(amount) to store the DP table.
How does the algorithm handle amounts that cannot be formed, such as amount 3 with coins [2, 5]?
If an amount cannot be formed by any combination of the given coins, the DP state remains initialized to infinity (or amount + 1). After filling the table, if the target state is still unreachable, the function returns -1.
![Weights [1,2,3], values [6,10,12], W = 5 overview diagram](/blogs/0-1-knapsack-explained-packing-weights-1-2-3-up-to-capacity-5/diagrams/hero.svg)
![Find "ABCCED" on [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] overview diagram](/blogs/word-search-on-a-board-explained-finding-abcced-in-a-3-4-matrix/diagrams/hero.svg)
