Problem context and objectives
Mission briefing
Energy-route planner · A runner crosses a line of power stations
Build each decision from smaller outcomes already solved: The Fewest Coins.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when Minimum coin change matches the clues
- 2Keep this true after every move: dp[amount] is the fewest coins known to form that exact amount
- 3Reach the result within O(amount times coin count) time and O(amount) space
Rules and pressure
- Target cost: O(amount times coin count) time and O(amount) space
- State rule: dp[amount] is the fewest coins known to form that exact amount
Lesson 1 of 3
Live algorithm trace
Minimum coin change
Complete execution1 of 6
Seed amount zero and mark positive amounts unreachable.
1
dp[0] = 0; others infinity2
for amount from 1 through target3
for each coin not exceeding amount4
candidate = dp[amount - coin] + 15
keep the minimum candidate6
return -1 if target remains infinitytarget = 11dp0 = 0
Truth to preserve / Cost target
Truth to preserve
dp[amount] is the fewest coins known to form that exact amount
Cost target
O(amount times coin count) time and O(amount) space
For every amount, try making one final coin choice after an already solved smaller amount. Unlimited reuse is natural because that smaller state may contain the same coin.
Your call · What should guide every step of this algorithm?