codaBack to Academy
dynamic programming
Coin Change
The Coin Change problem determines the minimum number of coins needed to make a given amount. Given an array of coin denominations and a target amount, we build a 1D DP table where dp[i] represents the fewest coins needed to make amount i. For each amount, we try every coin denomination and take the minimum. If no combination can reach the target, the result is -1. This is a classic unbounded knapsack variant.
Use Cases
- •Currency exchange and making change in financial systems
- •Resource minimization problems in operations research
- •Optimal token or ticket dispensing in vending machines
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(n * amount) | O(n * amount) | O(n * amount) |
| Space | O(amount) | ||
Visualization
| F(0) | F(1) | F(2) | F(3) | F(4) | F(5) | F(6) | F(7) | F(8) | F(9) | F(10) | |
|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Implementation
Output
Click "Run Code" to see output...