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.

Input: coins=[1, 2, 5], amount=11  → 3   (5+5+1)
Input: coins=[1, 5, 11], amount=15 → 3   (5+5+5)
Input: coins=[2], amount=3         → -1  (unreachable)

Verification

Trace coins=[1,5,6,9], amount=11: dp[0]=0. dp[5]=dp[0]+1=1. dp[6]=dp[0]+1=1. dp[10]=dp[5]+1=2. dp[11]=min(dp[10]+1=3, dp[5]+1=2, dp[2]+1=inf) = 2 via dp[5]=1 (11-6=5, dp[5]+1=2).

Solution

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, 5, 6, 9] for 11: greedy grabs 9 then cannot make 2 cheaply, while DP finds 5 + 6 = 2 coins by reading dp[5] + 1.

Edge cases: amount = 0 returns 0 immediately via dp[0]. An unreachable target (e.g. [2] for 3) 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.