Dynamic Programming · 034Medium
Coin Change
Given an array of coin denominations and an integer amount, return the fewest coins needed to make up that amount, or -1 if it is impossible. You have an infinite supply of each coin.
Constraints
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
Examples
coinChange([1, 2, 5], 11) -> 3 // 5 + 5 + 1 coinChange([2], 3) -> -1 coinChange([1], 0) -> 0 coinChange([1, 3, 4], 6) -> 2 // 3 + 3; greedy 4+1+1 would give 3 coinChange([3, 7], 11) -> -1 // no combination reaches 11 coinChange([2, 5, 10, 1], 27) -> 4 // 10 + 10 + 5 + 2
Edge cases
- Amount 0 needs 0 coins.
- An unreachable amount returns -1, not Infinity.
Show the target complexity (spoiler)
- Naive
- O(amount^coins) time — recurse over every combination.
- Target
- O(amount * coins) time, O(amount) space — bottom-up DP where dp[a] = 1 + min(dp[a - c]) over all coins c.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/034-coin-change.js ./practice c 034