Coin Change

Given coin denominations and a total amount, return the fewest number of coins needed to make that amount. Return -1 if impossible. Greedy fails for many coin systems.

Why this is worth learning

Amounts form a directed acyclic graph when every coin is positive: taking a coin moves from a smaller amount to a larger one. The desired value is a shortest path measured in coin count.

Before coding: one-minute experiment

With coins [1,3,4] and amount 6, why does greedy choose three coins while DP chooses two?

Function signature

func CoinChange(coins []int, amount int) int

Inputs / outputs

• coins: available denominations.
• amount: target sum.
• Return: minimum number of coins, or -1.

Example

coins = [1,2,5], amount = 11
Best: 5 + 5 + 1 -> 3
Output: 3

Constraints

• 0 <= amount <= 10_000
• 1 <= len(coins) <= 100
• Every denomination is a positive integer; duplicates are allowed and do not change the result.

Core idea (near-solution)

DP where dp[i] is the fewest coins to make amount i. Transition from dp[i-coin].

Invariant: dp[i] is minimal after considering all coins.

Algorithm (step-by-step)

1. Initialize dp[0]=0 and dp[i]=INF for i>0.
2. For i from 1..amount:
   • For each coin c:
     • If i>=c, dp[i]=min(dp[i], dp[i-c]+1).
3. If dp[amount] is INF, return -1; else return dp[amount].

Correctness sketch

Let C(a) be the minimum number of coins totaling amount a, or unreachable. C(0)=0. Every nonempty solution for a has some last denomination c<=a and a solution for a-c; replacing that prefix with its optimum cannot worsen the count. Conversely adding c to any reachable a-c makes a feasible solution. Therefore C(a)=min(C(a-c)+1) over eligible denominations. Positive coins ensure predecessors are strictly smaller and already computed in increasing amount order. The sentinel amount+1 exceeds every possible feasible minimum because positive integer coins require at most amount coins.

Trace (hand walkthrough)

Example input:
coins = [1,2,5], amount = 11
Best: 5 + 5 + 1 -> 3
Output: 3

Walk:
- dp[0]=0, dp[1]=1, dp[2]=1, dp[5]=1
- dp[10]=2 (5+5), dp[11]=3 (5+5+1)

Pitfalls to avoid

• Forgetting to initialize dp with a large sentinel.
• Returning dp[amount] even when unreachable.

Debugging lens

Test amount zero, unreachable residues, duplicate denominations, and coins larger than the amount. Only positive denominations satisfy the recurrence and indexing contract. Never read dp[a-c] when c>a.

Complexity

• Time: O(amount * len(coins)).
• Extra space: O(amount).

Implementation notes (Go)

• Set INF to amount+1 to stay within int bounds.

Contract precision

Coins must be positive integers and amount must be nonnegative (the stated upper bound remains 10000). Zero/negative denominations are not supported by the existing API; negative coins can cause out-of-range indexing.

Reconstruction checkpoint

With coins [1,3,4] and amount 6, why does greedy choose three coins while DP chooses two?

Return to 1D DP (Including Kadane) · Module quiz