Coin Change
Find the minimum number of coins needed to make a target amount. Classic dynamic programming problem with applications in finance and optimization.
IntermediateTime: O(n × m)Space: O(n)
Coins: [1, 2, 5]
Step 1 / 0
Current Step
Click Play to start the visualization
## How Coin Change with DP Works
The Coin Change problem asks: what's the minimum number of coins needed to make a target amount? This is a classic dynamic programming problem.
### Algorithm Steps:
1. Create a DP array where dp[i] = min coins for amount i
2. Initialize dp[0] = 0 (0 coins for amount 0)
3. For each amount i from 1 to target:
- For each coin c: dp[i] = min(dp[i], dp[i-c] + 1)
4. Return dp[target]
### Key Characteristics:
- **Unbounded**: Can use each coin unlimited times
- **Optimal Substructure**: Solution builds on smaller amounts
- **Bottom-up DP**: Fill table from 0 to target amount
Time & Space Complexity
| Case | Time Complexity |
|---|---|
| Best | O(n × m) |
| Average | O(n × m) |
| Worst | O(n × m) |
| Space | O(n) |
Practice Problems
No Problems Available
Practice problems for this algorithm are coming soon!