Minimum Coin Change

Minimum coin change works by building up the cheapest way to form every amount from 0 up to the target, reusing already-solved smaller amounts — for each amount a the best answer is 1 + min(dp[a - c]) over every coin c you're allowed to use, because the last coin placed in any optimal solution splits the problem into 'one coin' plus 'an optimal solution to the remainder'.

Recognize the pattern

• "Minimum/maximum number of ways/items to reach a target" with an unlimited/limited supply of building blocks (coins, denominations, jumps).
• The blocks are reused (unbounded) or each used once (0/1) — a single word like "infinite supply" signals unbounded knapsack-style DP.
• The answer to amount a only depends on answers to smaller amounts a - c — an optimal-substructure recurrence, not a greedy pick.
• Greedy (always take the biggest coin) is tempting but provably wrong for arbitrary denominations (e.g. {1,3,4}, amount 6: greedy gives 4+1+1=3 coins, optimal is 3+3=2).

Brute force to optimal

Brute force: recursively try every coin at every remaining amount: f(a) = 1 + min over c of f(a-c), base case f(0)=0. Without memoization this recomputes the same sub-amounts exponentially many times. A loose upper bound treats each call as branching into up to n children and the recursion depth as at most a (using the smallest coin, value 1, repeatedly) — giving O(n^a) as a worst-case ceiling, not an exact count. The real tree is uneven: a branch that picks a coin of value k descends by k each step, so branches using larger coins bottom out sooner and the true node count is smaller than n^a in practice, though still exponential without memoization.

Optimal (bottom-up DP): compute dp[0..amount] once, left to right, each entry in O(n). No overlapping call is ever redone.

Complexity, derived

There are amount + 1 subproblems (one per integer amount from 0 to T). Each subproblem tries all n coins once. So total operations = (amount+1) × n → Time O(n · amount). Space: one 1-D array of size amount+1 holding the best-count-so-far → Space O(amount) (O(1) extra beyond the table; no recursion stack since it's iterative).

Worked example

Denominations {1,2,3}, amount = 5. dp[a] = min coins to make a, dp[0]=0.

dp[5] = 2, matching {2,3}. Note the tie at a=5: coin 2 from dp[3] and coin 3 from dp[2] both yield 2 — min() just keeps the first value that achieves the minimum, it does not prefer one coin over the other.

Reference implementation (Java)

import java.util.Arrays;

class Solution {
    int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // sentinel > any real answer
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Pitfalls

• Greedy substitution: taking the largest coin first fails for non-canonical coin systems (e.g. {1,3,4}, amount 6).
• Sentinel overflow: using Integer.MAX_VALUE then adding 1 wraps to a negative number — use amount+1 as the 'unreachable' sentinel instead.
• Off-by-one on the loop bound: iterating coins before amounts (or vice versa) is fine for *minimum coins* (order doesn't matter), but flips the answer if you reuse this template for *counting distinct combinations* — that variant is order-sensitive.
• Forgetting the unreachable case (amount can't be formed) — must return -1, not a garbage large number.

When to use / when not

Use bottom-up 1-D DP when amount is bounded and reasonably small (fits O(n·amount) time/space, per the constraints here up to 5000). Alternative — BFS over amounts: treat each amount as a graph node, each coin as an edge; BFS from 0 finds the minimum coin count as the shortest path. Same O(n·amount) worst case, but BFS can stop early once the target is dequeued, and is more intuitive when denominations are also constrained to a set of allowed moves (like word-ladder-style problems). DP is preferred when you also need every dp[a] for a < amount (e.g. for reconstruction or reuse), or when repeated queries against the same coin set make one O(n·amount) preprocessing pass worthwhile. Neither DP nor BFS is ideal when amount is huge (e.g. 10^9) — that needs number-theoretic tricks or is intractable in general.

Takeaways

• Optimal substructure: dp[a] = 1 + min(dp[a-c]) over coins c ≤ a; base dp[0]=0.
• O(n·amount) time, O(amount) space — derived directly from (subproblems × choices per subproblem).
• Greedy is a trap: it only works for canonical coin systems; DP is always correct.
• Same recurrence template extends to coin-change-2 (count ways) by swapping the loop order and the combine operation from min+1 to sum.

Recall: Why does building dp strictly left-to-right from amount 0 upward guarantee dp[a-c] is already correct when you compute dp[a]?

Source: adapted from classic unbounded-knapsack coin-change formulations (e.g. LeetCode 322 / Educative-style course material).