Coin Change

Problem

Payment processing systems compute exact change using available denominations to minimize transaction overhead. Given an array of coin denominations and a target amount, return the minimum number of coins needed to make the amount. If the amount cannot be made, return -1.

Example 1:

Input: coins=[1, 3, 4], amount=6
Output: 2
Explanation: 3+3 = 6. Greedy largest-first would take 4+1+1 - three coins - but two 3s win.

Example 2:

Input: coins=[2, 5, 7], amount=12
Output: 2
Explanation: 5+7 = 12.

Example 3:

Input: coins=[4], amount=7
Output: -1
Explanation: No combination of 4-coins sums to 7.

Constraints:

• 1 <= coins.length <= 20
• 1 <= coins[i] <= 100
• 0 <= amount <= 2000

Verification

Trace coins=[3,5,8], amount=12: dp[0]=0. dp[3]=dp[0]+1=1. dp[6]=dp[3]+1=2. dp[9]=dp[6]+1=3. dp[12]=min(dp[9]+1=4, dp[7]+1=inf, dp[4]+1=inf) = 4 via three 3-coins plus one more (3+3+3+3).

Solution Breakdown

Approach: 1D bottom-up tabulation over the target amount (unbounded knapsack).

Define dp[a] as the fewest coins needed to make amount a. Any optimal way to make a ends with some last coin c; remove it and what remains is an optimal way to make a - c, which is dp[a - c]. So dp[a] is one more than the cheapest reachable dp[a - c] across every coin that fits. The outer loop fills amounts from 1 up to the target, and for each it tries every coin c <= a, taking min(dp[a], dp[a - c] + 1). Coins may repeat because dp[a - c] is already a finished optimal answer that itself can reuse c, which is what makes this the unbounded variant. Initialization is the crux: dp[0] = 0 (zero coins make zero), and every other entry starts at float('inf') to mean "not yet reachable". Infinity propagates correctly - adding 1 to infinity stays infinity - so an amount no combination can build stays infinite, and the function maps it to -1. This is why greedy loses on [1, 3, 4] for 6: greedy grabs 4 then must cover 2 with two 1-coins for a total of 3, while DP finds 3 + 3 = 2 coins by reading dp[3] + 1.

Edge cases: amount = 0 returns 0 immediately via dp[0]. An unreachable target (e.g. [4] for 7) leaves dp[amount] at infinity and yields -1.

Complexity: O(amount x len(coins)) time, O(amount) space - one table cell per amount, each scanned against all coins.