Stage 1 · Code
Dynamic Programming
Coin Change
Minimum coins for amount, number of ways variants.
6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Minimum Coins (Coin Change I)
Given coins of different denominations and a total amount, find minimum number of coins to make that amount. Return -1 if impossible. Unbounded knapsack: each coin can be used unlimited times.
Gocoin-change---minimum-coins.go
19 linesLn 1, Col 1Go
dp[i] = min coins for amount i. Initialize with amount+1 (infinity). For each amount, try all coins. Unbounded: iterate amounts forward. O(amount × n) time, O(amount) space.
Number of Ways (Coin Change II)
Given coins and amount, find number of combinations to make amount. Order of coins doesn't matter (combinations, not permutations).
Gocoin-change-ii---number-of-ways.go
12 linesLn 1, Col 1Go
Key: iterate coins OUTER, amounts INNER. This ensures each combination counted once regardless of coin order. dp[i] += dp[i-c] means add ways using current coin.
Variants
| Variant | Problem | Key Difference |
|---|---|---|
| Min coins | Fewest coins for amount | Min over choices, init with INF |
| Num ways | Total combinations | Sum over choices, init dp[0]=1 |
| Exact change | Can we make exact amount? | Boolean DP: dp[i] = dp[i] || dp[i-c] |
| Limited coins | Each coin has max count | Multiple knapsack or binary splitting |
| Ordered ways | Permutations (order matters) | Iterate amounts OUTER, coins INNER |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.