Coin change · minimum coins

Use amount states to find the fewest coins for a target, allowing unlimited reuse of each denomination.

Remember: Best smaller amount + one coin.

Example: Coins [1,3,4], amount 6 → two coins [3,3]; greedy [4,1,1] uses three.

Time: O(kA). Auxiliary space: O(A).

Formula: dp[0] = 0; dp[s] = min(dp[s], 1 + dp[s−coin]) when coin ≤ s

Up to 15 distinct positive denominations; unlimited reuse. Amount A from 0 to 20. ∞ means unreachable; result −1 means no solution. k is the number of denominations. O(kA) is pseudo-polynomial in the numeric amount. Predecessors recover one optimal combination. Greedy largest-first can fail.

Complexities describe the underlying algorithm; tutorial snapshots and rendering can use additional resources.

The interactive workspace loads here when JavaScript is available. You can still browse the learning notes and links above without it.