“Know how to solve every problem that has been solved.” “What I cannot create, I do not understand.” — Richard Feynman

Coin Change Problem

Algorithms

You've got a target amount $T$ and a list of coin denominations. Two related questions: what's the fewest coins that sum to $T$ , and how many distinct combinations of coins sum to $T$ ?

Dynamic programming approach

Keep one array, $d p$ , of length $T + 1$ . $d p [x]$ means different things depending on which version you're solving. For the fewest-coins question, $d p [x]$ is the minimum number of coins that sum to $x$ . For the number-of-ways question, $d p [x]$ is the count of distinct combinations that sum to $x$ . The algorithm is roughly the same in both cases. The only difference is the update rule for $d p$ .

Time complexity

Each cell of $d p$ fills in constant time by looking back at smaller cells. With $n$ coin denominations and target $T$ , the whole thing runs in $O (n \cdot T)$ .

Implementation

def coin_change_min_coins(coins, T):
    """Minimum number of coins that sum to T, or -1 if impossible."""
    dp = [float('inf')] * (T + 1)
    dp[0] = 0
    for x in range(1, T + 1):
        for coin in coins:
            if x >= coin:
                dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[T] if dp[T] != float('inf') else -1


def coin_change_num_ways(coins, T):
    """Count of distinct coin combinations that sum to T."""
    dp = [0] * (T + 1)
    dp[0] = 1
    for coin in coins:
        for x in range(coin, T + 1):
            dp[x] += dp[x - coin]
    return dp[T]


# Example: target 11 with coins {1, 2, 5}.
coins, T = [1, 2, 5], 11
print(coin_change_min_coins(coins, T))   # 3   (e.g., 5 + 5 + 1)
print(coin_change_num_ways(coins, T))    # 11

Try First

Each prompt asks a checkable question about the working code or math above — predict an output, derive a sign, state an invariant, find a bug. Commit to an answer before clicking "reveal." That commitment is the whole point: if your answer matched, you understand the piece you were looking at; if it didn't, that's the part worth re-reading.

invariant

In coin_change_num_ways, suppose the outer loop has finished processing the first k coins (so the next iteration would start for coin in coins[k:]). What does dp[x] mean at this moment? Be precise about which set of objects is being counted — including which coins are eligible and what orderings count as the same.

why does this work

coin_change_num_ways initializes dp[0] = 1. But there's no coin and no positive amount yet — what "way" is being counted? Predict what happens if you set dp[0] = 0 instead. Predict what happens if you set it to 2.

trace

Trace coin_change_min_coins([1, 2, 5], T=6) by writing out the full dp array as it gets filled. Note where each cell's value comes from. Then verify the answer matches your mental check: the fewest coins summing to 6 should be 2 (5 + 1) or (1 + 5) — same thing.

find the bug

For real US coins [1, 5, 10, 25], the greedy algorithm ("always take the largest coin that fits") gives the optimal answer. For [1, 3, 4] with T = 6, greedy gives 4 + 1 + 1 = 3 coins; the DP gives 3 + 3 = 2 coins. Construct another coin set where greedy fails, and articulate the property that distinguishes greedy-safe coin sets from greedy-unsafe ones.

predict

Without running the code, predict the order of magnitude of coin_change_num_ways([1, 2, 5], T=1000). Then predict T = 10000. Why does this count grow so fast in T?

Hack This

The code above works. Don't reinvent it — pull it into an editor, run it, and try the modifications below. Each one is small. Each one will change the behavior in a specific way; the question is which way.

trivial

Swap the loop order in coin_change_num_ways: change for coin in coins: for x in range(coin, T+1) to for x in range(1, T+1): for coin in coins:. Run it on coins=[1, 2, 5], T=5. The original returns 4; the swapped version returns 9. The function still works — but it's now counting something different. Write out the four (or nine) things being counted, and articulate the rule that distinguishes them.

hint

The four combinations of [1, 2, 5] summing to 5: {5}, {1, 2, 2}, {1, 1, 1, 2}, {1, 1, 1, 1, 1}. The nine ordered sequences include those four plus reorderings: e.g., {1, 2, 2} has 3 orderings (1-2-2, 2-1-2, 2-2-1) and {1, 1, 1, 2} has 4 orderings. 1 + 3 + 4 + 1 = 9. The "loop order is the canonicalization rule" framing is the key insight here — when you pick which loop is outer, you commit to an order in which decisions are made.

small

Replace min with max in coin_change_min_coins and change the initial value from float('inf') to float('-inf'). Run on coins=[1, 2, 5], T=11. The answer becomes 11 (eleven 1-coins). When is "maximum number of coins" a meaningful business problem? And: what subtle thing happens if 1 isn't in your coin set?

hint

Real applications: maximizing the number of TRANSACTIONS in a bank-stress test, maximizing chips dealt in a poker simulation, any case where the "coin" represents an individual event and you want to bound how many can occur. Without 1 in the coin set, not every target is reachable — the answer is -inf for unreachable targets, which the algorithm needs to handle the same way it handles infeasibility in the min version.

small

min_coins returns the count but not which coins. Modify it to also return the actual list of coins that achieves the minimum. Use the standard DP-with-witness pattern: at each cell, record which coin's transition was chosen, then walk backward. Verify on coins=[1, 2, 5], T=11 — you should get [5, 5, 1] or any permutation totaling 11 with 3 coins.

hint

Keep a parallel choice array of length T+1. When dp[x] gets updated by coin, also set choice[x] = coin. To reconstruct: start at x = T, append choice[x], set x -= choice[x], repeat until x == 0. The result is one valid optimum (there may be others).

small

Constrain the unbounded problem: you have k_i coins of denomination c_i, not unlimited. Modify num_ways to take a parallel list counts and respect it. This is the "bounded knapsack" version. What's the new time complexity? Can you still get O(T) space per coin, or does bookkeeping grow?

hint

Inside the outer "for coin" loop, instead of one inner sweep, do k_i + 1 sweeps — one for "use this coin zero times," "use this coin once," ..., "use this coin k_i times." Or use the "monotonic queue" trick to do all k_i copies in O(T) total. Naive bounded knapsack is O(T · sum(k_i)); the monotonic-queue version is O(T · len(coins)), matching the unbounded case.

medium

Generalize min_coins in a direction it doesn't usually go: each coin has both a denomination c_i AND a value v_i. Maximize total value subject to total denomination equaling T exactly, with unlimited copies of each coin. You've just written unbounded knapsack. Notice the structural identity: the recurrence's shape is identical to coin change; only what you're optimizing has changed. Articulate the general principle.

hint

Recurrence: dp[x] = max(dp[x - c_i] + v_i) for each coin c_i with c_i <= x. Min coins is the special case v_i = 1 and max replaced by min. Counting ways is the special case where +v_i is replaced by + dp[x - c_i] and you sum instead of optimize. Same DAG, three problems — another instance of the semiring-DP pattern (cf. the House Robber opening mod).

medium

Compute num_ways([1, 2, 5], T=20) two ways: (a) using the DP above; (b) by extracting the coefficient of

x^{20}

in the formal power series

\frac{1}{( 1 - x ) ( 1 - x ^{2} ) ( 1 - x ^{5} )}

. Verify they agree. The DP is computing the same coefficient — just iteratively, by repeatedly multiplying by the next factor. Modify the code so that the connection to generating functions is visible in the structure (e.g., maintain an explicit polynomial as a list of coefficients, multiply one factor at a time).

hint

Each factor

1/ (1 - x^{c}) = 1 + x^{c} + x^{2 c} + x^{3 c} + \dots

is what "unlimited copies of denomination c" looks like as a power series. Multiplying these factors together produces the generating function whose coefficients count the number of ways. The DP's inner loop is precisely the coefficient-by-coefficient polynomial multiplication. num_ways with the loop order coin-outer/amount-inner is exactly "multiply polynomial by

1/ (1 - x^{c})

, one coin at a time."

Exercises

A full exercise set is available for this topic, structured as one worked example + 7 practice problems (across 7 surface contexts) + 2 pattern-resistant check problems.

Open the Coin Change & Dynamic Programming exercise set → Recognize a problem as having overlapping sub-problems and optimal substructure; identify a state variable and a recurrence that combines smaller solutions into larger ones; tabulate from the base case upward in O(states × choices) time.