Overview
Find the minimum number of coins from a given set to make an exact target amount.
Analogy
Making change at a register: use fewest bills/coins to make exact change.
Step-by-step
- dp[0]=0; dp[i]=∞ for i=1..amount.
- For each coin c and each amount i≥c: dp[i] = min(dp[i], dp[i-c]+1).
- If dp[amount] is still ∞, return -1 (impossible).
Visual
coins=[1,2,5], amount=11: dp=[0,1,1,2,2,1,2,2,3,3,2,3] → dp[11]=3 (5+5+1)
Common mistakes
- Initializing dp[0]=1 instead of 0.
- Greedy (always take largest coin) doesn't work for arbitrary coin sets.
Practice questions
- Count the number of ways (not minimum) to make the amount.
- Reconstruct the actual coins used.
AI Wisdom