Dynamic programming · minimum coins

Initialize · base case

Give amount 0 a known answer

Base case

Start with the simplest caseInitialize

Memory tabledp[x] = minimum coins

✓ Final · click an amount to jump

Index by amount (u = currency unit). Large numbers count coins; Last is the denomination stored in choice.

Apply the rules step by step

Follows the animation

Stage

General rule · why

At this step · apply the rule

This round’s candidates

Check every denomination

01
InitializeAmount 0 needs 0 coins
02
Select amount xIn order: 1 → 6
03
Try final coin cRead a smaller amount’s answer
04
Compare and updateReplace only if smaller
05
Finalize the amountSave count and final denomination
06
Recover the full pathFollow choice back to zero

③ ↔ ④ Try remaining denominations
② → ⑤ Then solve the next amount

Algorithm operation

Why this works

The rule throughout

Candidate count = dp[x − c] + 1

Try only c ≤ x. Update if the candidate is smaller; otherwise keep the old record.

What the symbols and loops mean

x: this round’s amount, in currency units.
c: assumed final denomination, in currency units.
dp[x]: minimum coins for amount x. Provisional during the round, final at its end.
choice[x]: the solution’s final denomination.

Six outer rounds cover amounts 1 → 6, each trying c = 1, 3, 4. The 50 animation steps separate operations; they are not 50 rounds.

If a smaller amount is ∞, no usable solution exists; ∞ + 1 is still ∞. Coin 1 makes every smaller amount reachable in this example.

01 / 50Initialize