218. Coin Change

Define dp[a] = the minimum number of coins that sum to amount a. To make a, the last coin used has some value c from the coin list — so dp[a] = 1 + dp[a - c] for some choice of c. We don't know which, so we try all coins and take the minimum.

The recurrence

dp[a] = min(dp[a - c] + 1) over all coins c with c <= a. With base case dp[0] = 0 (zero coins needed for amount zero) and a sentinel INF for unreachable amounts.

Steps

1. Set INF = amount + 1 (any value > amount works as sentinel — you can never need more than amount coins to make amount).
2. Initialise dp = [0] + [INF] * amount.
3. For each amount a from 1 to amount:
   • For each coin c:
     • If c <= a, update dp[a] = min(dp[a], dp[a - c] + 1).
4. Return dp[amount] if reachable (<= amount), else -1.

Walk-through

coins = [1, 2, 5], amount = 11.

dp starts as [0, INF, INF, ..., INF].

Result: 3 (e.g., 5 + 5 + 1).

Why bottom-up vs top-down

Top-down memoised recursion solves the same recurrence but introduces function-call overhead and hits Python's recursion limit on large amounts. Bottom-up iteratively fills the table in one pass.

Why greedy doesn't work in general

"Always pick the largest coin that fits" works for [1, 5, 10, 25] but not for [1, 3, 4] with amount 6: greedy picks 4 + 1 + 1 = 3 coins, but the optimum is 3 + 3 = 2 coins. DP examines all options.

Edge cases

• amount == 0: dp[0] = 0, return 0.
• No coin combination sums to amount: dp[amount] stays at INF, return -1.

Complexity

• Time: O(amount · n) where n = len(coins).
• Space: O(amount).

import java.util.*;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a && dp[a - c] + 1 < dp[a]) {
                    dp[a] = dp[a - c] + 1;
                }
            }
        }
        return dp[amount] <= amount ? dp[amount] : -1;
    }
}

Model the problem as a graph: each amount 0..amount is a node, and there's an edge from a to a + c for each coin c. Then "minimum coins" becomes "shortest path from 0 to amount" — exactly what BFS computes.

Why BFS is shortest-path

BFS visits nodes in non-decreasing distance order from the source. Distance here is the number of edges, which is the number of coins used. So the first time we reach amount, the BFS depth equals the minimum coin count.

Steps

1. Trivial case: if amount == 0, return 0.
2. Initialise seen = {0} and q = deque([(0, 0)]) (current amount, coins used).
3. While the queue is non-empty:
   • Pop (a, k).
   • For each coin c:
     • na = a + c.
     • If na == amount, return k + 1.
     • Else if na < amount and na not in seen, add to seen and enqueue (na, k + 1).
4. If BFS exhausts, return -1.

Walk-through

coins = [1, 2, 5], amount = 11.

BFS levels (showing amounts, not full tuples):

Level 0: {0}
Level 1: {1, 2, 5}
Level 2: {3, 4, 6, 7, 10}
Level 3: {8, 9, 11}   ← 11 found at depth 3 → answer is 3

Why this is O(amount · n)

Each amount enters seen at most once. When dequeued, we try n coin extensions. So total work is O(amount · n) — same as the DP, but with constant factors that depend on whether BFS happens to reach the goal early.

When BFS beats the DP

• Cache locality: the DP fills a contiguous array, often faster in practice.
• BFS can short-circuit if the goal is reached at a shallow depth — useful if the answer is small.

Edge cases

• amount == 0: the early return.
• Unreachable: BFS exhausts; return -1.

Complexity

• Time: O(amount · n).
• Space: O(amount) for seen and the queue.