Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the *fewest number of coins* that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Examples
coins = [1,2,5], amount = 113coins = [2], amount = 3-1coins = [1], amount = 00coins = [1,2,5], amount = 51Constraints
1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4
š” Hints
Hint 1
Think bottom-up: to make up amount i, consider taking coin c and adding 1 to the optimal solution for amount (i - c).
Hint 2
Initialize an array dp of size amount + 1 with Infinity. Base case is dp[0] = 0.
Hint 3
For each amount from 1 to amount, iterate over all coins that are <= current amount and take the minimum.
Algorithm Complexity
Official asymptotic Big-O runtime and auxiliary memory analysis
Bottom-up 1D dynamic programming. dp[i] represents the minimum coins needed for amount i. Transition: dp[i] = min(dp[i], dp[i - coin] + 1).
Iterates through each sub-amount from 1 to amount, trying each of the available coins in inner iteration in O(amount * coins.length).
A 1D dynamic programming table of size (amount + 1) stores the minimum coin counts.
š Real-World Use Cases
Determining the minimal set of bill/token denominations required to satisfy merchant cash transfers using 1D dynamic programming.
š Dry Run
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| dp | 0 | ā | ā | ā | ā | ā |
Initialize dp table of size 6 for amount = 5. Base case: dp[0] = 0 coins needed for amount 0.