visual-cs /
Coin Change
← Back
Coins (comma-separated)
Classic
Greedy-friendly
Impossible
US Coins
No 1
Amount
▶ Play
⏸ Pause
⏭ Step
↺ Reset
Speed
5
Amount
11
Coin Used
—
Updates
0
Phase
—
Min Coins
—
Coins
DP Table — dp[amount]
Legend
Not yet computed
Current cell being filled
Candidate value (dp[a-c]+1)
Cell improved (new minimum)
Traceback path
Coins Used
Step Log
How It Works
Recurrence:
dp[0] = 0
dp[a] = min(dp[a-c]+1)
for each coin
c ≤ a
Fill amounts
1 → target
. For each amount, try every coin that fits and keep the minimum count. If no coin reaches it,
dp[a] = ∞
.
Traceback:
from target, repeatedly follow
a → a - chosen_coin
until 0.
Complexity:
O(amount × coins) time, O(amount) space.