Making Change Visualizer
Watch how dynamic programming finds the minimum number of coins needed to make change for any amount.
Time: O(amount × coins)
Space: O(amount)
Bottom-up DP
Optimal substructure
Fast (300ms)Slow (2000ms)
Progress: Step 1 of 0Phase: start
Available Coins
1
4
5
DP Table (Minimum Coins Needed)
dp[0]
∞
amt:0
dp[1]
∞
amt:1
dp[2]
∞
amt:2
dp[3]
∞
amt:3
dp[4]
∞
amt:4
dp[5]
∞
amt:5
dp[6]
∞
amt:6
dp[7]
∞
amt:7
dp[8]
∞
amt:8
dp[9]
∞
amt:9
dp[10]
∞
amt:10
dp[11]
∞
amt:11
Current Step:
Click Start to begin the coin change visualization
Algorithm Details
Time Complexity:
O(amount × coins)Space Complexity:
O(amount)Type:Bottom-up DP
Pattern:Unbounded Knapsack
Real-world Applications
- •Cashier systems and vending machines
- •Currency exchange optimization
- •Resource allocation in systems
- •Inventory management
- •Network packet routing optimization
Key DP Concepts
- ✓Optimal Substructure: Optimal solution contains optimal subsolutions
- ✓Overlapping Subproblems: Same subproblems appear multiple times
- ℹRecurrence: dp[i] = min(dp[i], dp[i-coin] + 1)
- ℹBase Case: dp[0] = 0 (zero coins for amount 0)
Problem Variants
- •Count number of ways to make change
- •Maximum coins with limited supply
- •Minimum/maximum value with coin weights
- •Coin change with exact denominations