Coin Change
Find minimum coins needed to make a target amount.
How it works
The Coin Change problem asks: given coin denominations and a target amount, what is the minimum number of coins needed to reach that amount exactly? Unlike greedy approaches — which fail for arbitrary denominations (e.g., coins [1, 3, 4] and target 6: greedy picks 4+1+1=3 coins, but 3+3=2 coins is optimal) — the DP approach guarantees the globally optimal solution by solving every sub-amount first.
The bottom-up tabulation strategy builds a table dp[0..amount] where dp[i] stores the minimum coins to form amount i. The recurrence is dp[i] = min over all coins c where c ≤ i of (dp[i - c] + 1). The base case dp[0] = 0 anchors the recurrence: you need zero coins to make zero. For each amount i, we try every denomination and take the option that results in the fewest total coins. If no denomination can reach i (dp[i] remains ∞), the amount is declared impossible and stored as -1. Time complexity is O(n × amount) where n is the number of coin denominations, and space is O(amount).
This problem is structurally equivalent to the unbounded knapsack problem because coins can be reused any number of times. It also appears in disguise throughout software engineering: any time you need to decompose a value into the fewest discrete units — packet sizes, cache line boundaries, register allocations — the same DP recurrence applies. Mastering Coin Change unlocks a broad family of DP problems including Climbing Stairs, Word Break, and Combination Sum IV.
Complexity
Visualizer
Where it's used in the real world
ATM and cash dispensing systems
Optimal banknote combination for requested withdrawal amountsATMs must dispense exact amounts using available bill denominations (e.g., $100, $50, $20) while minimizing the number of bills used. Coin Change DP solves this in O(denominations × amount) at transaction time, handling irregular denomination sets that greedy algorithms would fail on.
Vending machines and point-of-sale terminals
Minimum-coin change-making for customer transactionsPOS systems compute optimal change to return using available coin inventory. When certain denominations are depleted, the greedy approach breaks down. The DP table is recomputed whenever coin inventory changes, ensuring the machine never claims change is impossible when it is actually achievable.
Currency exchange and remittance platforms
Minimizing transaction count in multi-currency settlementInternational payment networks decompose transfer amounts into standard lot sizes or SWIFT transaction units to minimize clearing fees. The Coin Change recurrence models available lot sizes as coin denominations, minimizing the number of sub-transactions needed to settle a large transfer.
Implementation
function coinChange(coins: number[], amount: number): number {
const dp = new Array<number>(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange([1, 3, 4], 6)); // 2 (3+3)
console.log(coinChange([2], 3)); // -1 (impossible)
console.log(coinChange([1, 5, 6, 9], 11)); // 2 (5+6)