Coin Change — The Exact Fare

Boss 8: The Exact Fare

Boss 7 counted paths through a string, summing every legal way to walk it. This boss keeps the walk but changes two things at once: the positions are no longer indexes into an array, they're amounts of money, and min replaces sum. You're not counting ways anymore, you're picking the cheapest one. What it installs: DP over a value range instead of an index range, unbounded reuse of items, and a scar to remind you why greedy needs a guarantee it doesn't have here.

The story

An old bus, an older fare machine. It takes exact payment only, no change, no mercy, and the driver watches you fumble. Your pocket holds unlimited coins in three denominations: 1, 3, and 4. The fare is 6. You'd like to feed the machine as few coins as possible, because the line behind you is growing.

Instinct says: biggest coin first.

greedy, biggest first:
  drop 4   (2 remaining)
  drop 1   (1 remaining)
  drop 1   (0 remaining)      3 coins

the passenger behind you:
  drop 3   (3 remaining)
  drop 3   (0 remaining)      2 coins

Greedy lost. The 4 looked like progress, but it stranded you on 2, a territory only reachable by two clunky 1s. The 3 looked like less progress and set up a perfect second step. With denominations like these, no rule of thumb about "big first" or "big last" survives, the only way to know the best play for 6 is to know the best play for the amounts underneath it.

The problem, dressed up properly

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

LeetCode 322.

The naive attempt

Code the instinct:

def coin_change_greedy(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):   # biggest first
        while amount >= c:
            amount -= c
            count += 1
    return count if amount == 0 else -1

On coins = [1, 3, 4], amount = 6: returns 3. The real answer is 2. Worse, on coins = [3, 4], amount = 6: greedy takes the 4, strands on 2, and returns -1 for an amount that two 3s pay perfectly. Greedy isn't just suboptimal here, it's wrong about reachability.

Greedy does work for canonical coin systems (US and EU coins are designed so it does). But nothing in this problem promises a canonical system, and interviewers pick denominations like [1, 3, 4] precisely to catch the assumption.

The weapon: unbounded knapsack over amounts

Build the answer for every amount from 0 up to the fare. Let dp[a] be the fewest coins that pay exactly a. Paying zero costs zero coins, so dp[0] = 0. For any other amount, the last coin dropped was some c, and before it the machine held a - c, paid optimally:

• dp[a] = 1 + the minimum of dp[a - c] over every coin c that fits.
• Amounts no combination can reach stay at infinity.
• Answer: dp[fare], or -1 if it's still infinity.

"Unbounded" is the keyword: the same coin can appear in the answer as many times as it likes, which is exactly what iterating over all coins at every amount gives you.

def coin_change(coins: list[int], amount: int) -> int:
    INF = float('inf')
    dp = [0] + [INF] * amount            # dp[a] = fewest coins paying exactly a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1    # drop coin c last
    return dp[amount] if dp[amount] != INF else -1

There's a second lens worth owning. Treat every amount as a node, and every coin as an edge from a to a + c. Then "fewest coins from 0 to fare" is literally "shortest path in an unweighted graph", and BFS from node 0 solves it level by level, Dungeon 11 style. The bottom-up table above computes the same distances in amount order instead of distance order. Two dialects, one truth: when every step costs 1, DP over values and BFS over a graph are the same walk.

Watching it work

coins = [1, 3, 4], fare 6:

dp[0] = 0
dp[1] = dp[0]+1 = 1                              (1)
dp[2] = dp[1]+1 = 2                              (1+1)
dp[3] = min(dp[2]+1, dp[0]+1) = 1                (3)
dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = 1       (4)
dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = 2       (4+1)
dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = 2       (3+3)
answer: 2 ✓

Look at dp[6]: the option through dp[5] (greedy's path, ending 4+1+1) costs 3, and the table calmly ignores it because the option through dp[3] costs 2. The table never argues with greedy. It just prices every route and takes the cheapest.

Gotchas

1. dp[0] must be 0, not 1. Paying nothing takes zero coins. Seed it with 1 and every answer inflates by one, quietly.

2. Returning the infinity sentinel raw. Whether you use float('inf') or the amount + 1 trick, an unreachable fare must come back as -1. Forgetting the final translation returns a nonsense number that looks like a coin count.

3. Skipping the c <= a bounds check. A coin bigger than the current amount indexes dp at a negative position, and Python's negative indexing will hand you a wrong value instead of a crash. The silent kind of bug.

4. Assuming greedy after this boss anyway. Greedy-by-biggest is only safe when the coin system is canonical, and no interview problem states that. If denominations are arbitrary, it's DP or BFS, no exceptions.

5. Fare 0. The answer is 0 coins, and the code above gets it right only because dp[0] = 0 and the loop never runs. Off-by-one the loop bounds and this edge breaks first.

Complexity

Every amount from 1 to the fare tries every coin once.

Time: O(amount × k) for k coin types. Space: O(amount).

Boss down. XP gained.

Two soft clinks, the machine blinks green, and the driver pulls away while greedy is still digging for its third coin. The fare was never a haggling match. It was a ladder of amounts, each rung priced from the rungs below it.

What you walked away with:

• Value-range DP: the table is indexed by amount, not by position in the input
• Unbounded reuse: looping all coins at every amount lets any coin appear any number of times
• Infinity as "unreachable", with a mandatory translation to -1 at the border
• The BFS lens: unit-cost choices over values are shortest paths in disguise
• Greedy needs a canonical-system guarantee, and [1, 3, 4] is the counterexample to carry

Next up: Boss 9 — The Hot Streak. Products instead of sums, where two negatives ambush you into a huge positive, and the only defense is tracking the worst case right alongside the best.