1. One-Liner
Coin change uses DP over amount (and sometimes coin index) to either minimize coins to reach S or count ordered/unordered ways, with unbounded supply per denomination.
2. The Problem It Solves
You have coin values c_i and target S. Classic tasks: fewest coins (or -1 if impossible), or number of combinations—definitions differ on order sensitivity; fix the loop order accordingly.
3. The Core Idea
Min coins: dp[x] = min over coins of 1+dp[x-c]. Count ways (combinations): outer loop over coins, inner over amount so each combination is counted once—avoid double-counting permutations.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1 | Init dp[0]=0 (min) or 1 (count) |
| 2 | For each amount x, relax using transitions |
| 3 | Handle impossible with ∞ or 0 |
| 4 | Return dp[S] |
5. Dry Run Example
Coins {1,3,4}, S=6: min coins 2 as 3+3; ways (combinations) depend on loop design—be explicit in interviews.
6. Key Properties
| Property | Value |
|---|---|
| Unbounded | Reuse coins |
| Pseudo-poly | In S and n |
7. Where It Is Used
| Domain | Use |
|---|---|
| Finance | Denomination breakdown |
| CP | Classic DP |
8. Interview Tips
Clarify min vs count, permutation vs combination, and greedy fails (counterexample: 1,3,4 vs amount 6).
9. Comparison with Other Algorithms
| Variant | Typical DP |
|---|---|
| 0/1 items | Knapsack—each once |
| Unbounded | Coin change—reuse |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n·S) typical |
| Space | O(S) |
Implementation Example (PYTHON)
def coin_change_min(coins: list[int], amount: int) -> int:
INF = amount + 1
dp = [INF] * (amount + 1)
dp[0] = 0
for x in range(1, amount + 1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], 1 + dp[x - c])
return -1 if dp[amount] > amount else dp[amount]