Senior · Algorithms
Dynamic programming: minimum coins
Why does choosing the largest coin first fail for arbitrary denominations?
Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.
ALGORITHM LAB · STEP THROUGH THE INVARIANT
coins [1, 3, 4], amount 6
Base case
Zero amount needs zero coins; ∞ means unreachable.
Computed traces for these inputs. Indexes identify cell positions; active cells are labeled as well as highlighted. Compare a boundary case using the scenario selector. No code is sent to a server.
func MinCoins(coins []int, amount int) int {
dp := make([]int, amount+1) // caller validates positive coins and bounded amount
for x := 1; x <= amount; x++ {
dp[x] = amount + 1
for _, c := range coins {
if c <= x && dp[x-c]+1 < dp[x] {
dp[x] = dp[x-c] + 1
}
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}Reveal a strong answer
Greedy choice needs a proof for the denomination system. With coins1,3,4 and amount6, greedy gives4+1+1 while3+3 uses fewer coins. Dynamic programming reuses optimal answers for smaller amounts.
Define dp[0]=0 and dp[x] as the minimum coins for x. For each positive coin c≤x, consider dp[x-c]+1 if that state is reachable. Initialize other states to an unreachable sentinel.
Reject nonpositive denominations and bound the amount before allocation. Reconstruct chosen coins with a predecessor array if needed. For huge amounts or different constraints, this pseudo-polynomial method may be unsuitable.
Common trap
A polynomial function of amount is not polynomial in the number of bits used to encode amount.
Complexity & use
O(amount × coinCount) time and O(amount) storage; pseudo-polynomial.
Try it
Compute dp[0..6] for coins1,3,4, then explain an unreachable case with coins2,4 and amount3.
Worked solution
The first table is0,1,2,1,1,2,2. With only2 and4, odd amounts remain unreachable, so return an explicit no-solution result. Test amount0, duplicates, invalid coins and a memory budget limit.
Change the constraint
How does changing the loop order alter a count-the-combinations problem?
How did you do?
Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.
Not marked. Progress stays on this browser, separate from course completion.
Primary references
Checked 2026-10-20. Use documentation for your pinned runtime, driver and tool version.