Coin Change

Learning goal: Translate coin combinations into a minimum-count optimization problem.

Core idea We are not looking for just any way to make the target; we want the construction with the fewest coins. Because coins may be reused, a solution can contain many copies of the same denomination. The central challenge is deciding which final coin belongs in an optimal construction.

What the answer means

For coins = [1, 3, 4] and amount = 6, the answer is 2 because 3 + 3 is better than 4 + 1 + 1, which uses three coins. If no combination reaches the target, return -1.

Algorithm plan

• Consider every smaller amount before solving the target.
• Record the smallest coin count known for each amount.
• Convert an unreachable sentinel into -1 only at the end.

Micro-example

• dp[0] = 0: making zero requires no coins.
• For amount 3, one coin of value 3 gives dp[3] = 1.
• For amount 6, using that result again gives dp[6] = 2.

Pitfalls

• Do not confuse the number of combinations with the minimum number of coins.
• The target may be zero, whose answer is 0.
• An unreachable amount must not be treated as a valid predecessor.

Recap

• Reuse is allowed, so earlier amounts can support later amounts.
• The output is a minimum, not a count of all solutions.
• Unreachable targets become -1.

Learning goal: Derive the recurrence from the identity of the final coin.

Core idea Imagine an optimal way to make amount a. Its last coin must have some denomination coin. Removing that coin leaves amount a - coin, and the remaining coins must themselves be optimal; otherwise we could improve the original solution. Therefore, try every coin that fits and keep the smallest result.

Recurrence

For every coin <= a:

dp[a] = min(dp[a], 1 + dp[a - coin])

The 1 counts the coin just added. Initialize dp[0] = 0 and every other state to infinity, represented by a value larger than any possible answer, such as amount + 1.

Micro-example For a = 6, coin 3 examines 1 + dp[3] = 2. Coin 4 examines 1 + dp[2] = 3, and coin 1 examines 1 + dp[5] = 3; the minimum is 2.

Pitfalls

• Only use dp[a - coin] when coin <= a.
• Infinity must never produce a usable candidate.
• The recurrence is a minimum, not a sum.

Recap

• Choose the final coin conceptually.
• Solve the leftover amount optimally.
• Take the minimum over all denominations.

Learning goal: Implement the recurrence in an order that guarantees every dependency is ready.

Core idea A state for amount a depends only on amounts smaller than a, because every usable coin is positive. That dependency direction gives a natural left-to-right fill order. By the time we compute dp[a], all possible dp[a - coin] values already exist.

Algorithm plan

1. Create an array dp of length amount + 1.
2. Fill it with amount + 1, acting as infinity.
3. Set dp[0] = 0.
4. For a from 1 through amount, try each coin.
5. If coin <= a, update dp[a] with min(dp[a], 1 + dp[a - coin]).
6. Return dp[amount] if it is reachable; otherwise return -1.

for a in range(1, amount + 1):
    for coin in coins:
        if coin <= a:
            dp[a] = min(dp[a], 1 + dp[a - coin])

Micro-example With target 6, the array begins as [0, ∞, ∞, ∞, ∞, ∞, ∞]. After processing amounts left to right, it becomes [0, 1, 2, 1, 1, 2, 2].

Pitfalls

• Use amount + 1 or another safe sentinel, not zero.
• Do not initialize each amount from a greedy coin choice.
• Check the sentinel before returning the final value.

Recap

• Increasing amounts respect all dependencies.
• Each state tries every denomination.
• The final state directly answers the problem.

Learning goal: Trace every one-dimensional DP state for coins = [1, 3, 4] and amount = 6.

Core idea We process amounts in increasing order and improve each state by testing all coins. The array is a compact record of solved subproblems: once dp[a] is finalized, larger amounts may reuse it. The visualization shows the best candidate after each amount is completed.

State progression

Micro-example At a = 6, the candidates are 1 + dp[5] = 3, 1 + dp[3] = 2, and 1 + dp[2] = 3. The minimum is 2.

Pitfalls

• A state can improve after considering a later coin in the inner loop.
• dp[4] = 1 does not imply greedy choices are globally correct.
• Keep the array indexed by amount, not by coin position.

Recap

• The completed array is [0, 1, 2, 1, 1, 2, 2].
• The answer is dp[6] = 2.
• The best combination is two coins of value 3.

Learning goal: Recognize why greedy selection is unsafe and how the DP handles boundaries.

Core idea A greedy strategy that repeatedly takes the largest coin can make an irreversible choice before seeing the best remainder. For coins = [1, 3, 4] and amount 6, greedy chooses 4, then two 1s, using three coins. DP compares that path with the overlooked choice 3 + 3, which uses only two.

Edge-case checklist

• Amount zero: dp[0] = 0, so return 0 immediately through the normal initialization.
• Coin larger than the amount: skip it because a - coin would be negative.
• Unreachable target: the sentinel remains unchanged, so return -1.
• Repeated use: processing increasing amounts allows dp[a - coin] to include the same denomination again.

Micro-example For coins = [2], amount 3, no transition reaches dp[3]. Its sentinel survives, so the answer is -1.

Pitfalls

• Never return the sentinel itself.
• Never assume common coin systems make greedy universally correct.
• Keep the base case separate from unreachable states.

Recap

• DP explores every final-coin choice.
• Greedy can fail even when a coin of value 1 exists.
• Sentinel detection handles impossible targets.

Learning goal: Analyze the resource cost and summarize the reusable DP pattern.

Core idea There are amount nonzero states, and each state examines every denomination. Thus the nested loops perform roughly amount * coins.length transitions. The array stores one answer per amount, so memory grows linearly with the target.

Complexity

Here, coins denotes the number of denominations, not their numeric values. The algorithm is usually preferable to recursive brute force because overlapping subproblems are solved once and reused.

Reusable pattern

1. Define a state for each subproblem.
2. Seed the empty/base state.
3. Fill states in dependency order.
4. Take the best transition.
5. Translate an unreachable sentinel into the requested output.

Micro-example For target 6 and three denominations, there are six nonzero states and at most eighteen coin checks. The resulting array ends with dp[6] = 2.

Pitfalls

• Write O(amount · coins.length), not exponential time.
• Space is O(amount), excluding the input array.
• A sentinel is an implementation detail, not a valid answer.

Recap

• Bottom-up DP is optimal and systematic.
• Time is O(amount · coins); space is O(amount).
• Return dp[amount] or -1 when unreachable.