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.

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

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

• Invariant: dp[i] is minimal after considering all coins.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

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.

Complexity

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

Implementation notes (Go)

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