Coin Change DP, in depth: finite tills, trillion-unit amounts, residue-class shortest paths and counting with Bostan-Mori

The reference table

For reference, the fewest-coins table. dp[a] is the minimum number of coins summing to a; dp[0] = 0 and every other entry is one more than the best dp[a - c] over coins c that fit. It costs O(n x A) time and O(A) memory for n denominations, and it is the oracle every faster method below is checked against.

INF = float("inf")

def min_coins(coins, amount):
    dp = [0] + [INF] * amount
    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
    return dp[amount]

A finite till: when stock breaks greedy

A cash machine loaded with 20s and 50s is the classic trap. The system {20, 50} with unlimited notes looks harmless, yet greedy already fails at 60: it takes a 50, leaves 10 and stops, while three 20s work. Add finite stock and failures multiply. Asked for 110 with three 20s left, greedy takes two 50s and is stuck on 10; the only answer is one 50 and three 20s. With only two 20s left, 110 cannot be paid at all and the machine must say so before it moves any notes.

The fix is a bounded DP over denominations. Process one denomination at a time; for each amount, try every count of that note from zero up to the stock. Because the till usually has a second objective, such as keeping scarce notes for later customers, the cost is a tuple compared lexicographically: fewest notes first, then fewest scarce notes. Keeping a per-denomination choice array lets you rebuild the exact dispense plan.

def dispense(stock, amount):
    """stock: {denomination: notes left}. Fewest notes, then fewest of the scarcest one."""
    denoms = sorted(stock)
    scarce = min(denoms, key=lambda d: stock[d])
    best = [None] * (amount + 1)
    best[0] = (0, 0)
    choice = []
    for d in denoms:
        new, pick = [None] * (amount + 1), [0] * (amount + 1)
        for a in range(amount + 1):
            for k in range(min(stock[d], a // d) + 1):
                prev = best[a - k * d]
                if prev is None:
                    continue
                cand = (prev[0] + k, prev[1] + (k if d == scarce else 0))
                if new[a] is None or cand < new[a]:
                    new[a], pick[a] = cand, k
        best = new
        choice.append(pick)
    if best[amount] is None:
        return None
    plan, a = {}, amount
    for i in range(len(denoms) - 1, -1, -1):
        if choice[i][a]:
            plan[denoms[i]] = choice[i][a]
        a -= choice[i][a] * denoms[i]
    return plan

dispense({20: 3, 50: 10}, 110)   # {50: 1, 20: 3}
dispense({20: 2, 50: 10}, 110)   # None: refuse before moving notes

The inner loop over k makes this O(A x total stock) in the worst case. Real tills have a handful of denominations and amounts in the low thousands of units, so it runs in microseconds. If stock counts get large, the inner loop can be replaced with a sliding-window minimum per residue class, which brings each denomination back to O(A).

Huge amounts: fewest coins from a small table

Suppose the amount is 10^12 and the largest coin is 9. The table is out of the question, but a pigeonhole argument shows it is also unnecessary. Let cmax be the largest coin and c2 the second largest. Take any collection of cmax coins that are each smaller than cmax. Their prefix sums take cmax values modulo cmax, so either one is zero or two coincide, and in both cases some non-empty subset sums to a multiple j x cmax. That subset has k coins each smaller than cmax, so j < k. Replacing it with j copies of cmax gives the same amount with strictly fewer coins.

So an optimal solution never uses cmax or more small coins, and the small coins in it sum to at most B = (cmax - 1) x c2. Everything above B is paid in largest coins. That lets you peel off a provable minimum number of largest coins and solve a remainder no bigger than B with the ordinary table.

def min_coins_large(coins, amount):
    coins = sorted(coins)
    top, second = coins[-1], (coins[-2] if len(coins) > 1 else 0)
    bound = (top - 1) * second            # small coins in any optimum sum to at most this
    q = max(0, -(-(amount - bound) // top))   # ceil((amount - bound) / top)
    rest = amount - q * top
    if rest < 0:
        return INF                        # would need more top coins than fit
    r = min_coins(coins, rest)
    return INF if r == INF else q + r

min_coins_large([1, 5, 6, 9], 10**12 + 7)   # 111111111113, from a 49-entry table

Both directions of the equality hold: an optimum for A contains at least q largest coins, so removing them leaves a solution for the remainder; and any solution for the remainder plus q largest coins pays A. Unreachable amounts stay unreachable for the same reason. For {1, 5, 6, 9} the bound is 8 x 6 = 48, so a trillion-unit query builds a table of at most 49 entries.

Huge amounts: is it payable at all?

Sometimes the only question is whether an amount can be paid: a voucher system that sells packs of 6, 9 and 20 credits needs to tell a customer instantly whether 1,000,003 credits is a valid order. Pick the smallest coin m and group amounts by their remainder modulo m. If amount x is payable then so is x + m, so each residue class is payable from some smallest member upward. Call that smallest member dist[r].

Computing dist is a shortest-path problem on just m nodes: from residue r, coin c leads to residue (r + c) mod m at cost c. Dijkstra's algorithm finds every dist[r] in O(n m log m), independent of how large the queried amounts are. After that, each query is one comparison.

import heapq

def residue_dist(coins):
    m = min(coins)
    dist = [INF] * m
    dist[0] = 0
    pq = [(0, 0)]
    while pq:
        d, r = heapq.heappop(pq)
        if d > dist[r]:
            continue
        for c in coins:
            nd, nr = d + c, (r + c) % m
            if nd < dist[nr]:
                dist[nr] = nd
                heapq.heappush(pq, (nd, nr))
    return m, dist

def payable(amount, table):
    m, dist = table
    return dist[amount % m] <= amount

def frobenius(coins):
    m, dist = residue_dist(coins)
    return None if INF in dist else max(dist) - m   # None: gcd above 1, gaps never end

frobenius([6, 9, 20])   # 43

The largest gap, max(dist) - m, is the Frobenius number: the biggest amount that cannot be paid. For {6, 9, 20} it is 43, so every order of 44 or more credits is valid. If the coins share a common factor, some residue classes are never reached and gaps continue forever, which the code reports as None.

Huge amounts: counting ways with a recurrence

Counting combinations for a huge amount uses generating functions. The number of ways to make N is the coefficient of x^N in 1 / ((1 - x^c1)(1 - x^c2)...), because each factor 1 / (1 - x^c) = 1 + x^c + x^2c + ... chooses how many copies of coin c to use. A coefficient of a rational function with denominator degree d satisfies a linear recurrence of order d, here d = c1 + c2 + ..., so the answer can be computed in O(d^2 log N) with the Bostan-Mori method: multiply numerator and denominator by Q(-x), which makes the denominator even, then keep only the even or odd coefficients according to the parity of N and halve N.

def polymul(a, b, p):
    out = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        if x:
            for j, y in enumerate(b):
                out[i + j] = (out[i + j] + x * y) % p
    return out

def ways_huge(coins, n, p=998_244_353):
    """[x^n] 1 / prod(1 - x^c) modulo p, in O(d^2 log n) with d = sum(coins)."""
    q = [1]
    for c in coins:
        q = polymul(q, [1] + [0] * (c - 1) + [p - 1], p)
    num = [1]
    while n:
        q_neg = [(-x) % p if i % 2 else x for i, x in enumerate(q)]
        num = polymul(num, q_neg, p)[n % 2::2]
        q = polymul(q, q_neg, p)[0::2]
        n //= 2
    return num[0] if num else 0

ways_huge([1, 5, 10, 25, 50], 100)     # 292, matches the table
ways_huge([1, 5, 10, 25, 50], 10**18)  # 60 halvings of a degree-91 polynomial

The method needs the sum of denominations to be modest, a few thousand at most with schoolbook multiplication. For US coins it is 91, so a 10^18 query takes about 60 rounds of small polynomial products. Verify it against the table for every N up to a few hundred; an off-by-one in the parity slice gives plausible but wrong numbers.

Failure modes

• Greedy on a finite till. Even a canonical system fails once a note runs out. Any dispenser that uses greedy must re-verify the plan against stock, and the honest fix is the bounded DP.
• Moving notes before proving feasibility. Plan the whole dispense, then actuate. A partial dispense that fails halfway needs a reversal path that most hardware does not have.
• Using the reduction bound with the wrong coin. The pigeonhole argument needs the largest coin and the second largest; sorting descending and indexing from the wrong end silently produces a bound that is too small, and the answer is off for some amounts only.
• Frobenius with a common factor. If the gcd of the coins exceeds 1, there is no largest gap. Check for unreachable residues instead of returning a misleading number.
• Counting without a modulus. Ways grow polynomially of degree n - 1 in N; for 10^18 they exceed 64 bits instantly. Fix the modulus in the API, or use big integers and accept the cost.
• Fast path never compared with the oracle. Every method here has a small-amount mode that the plain table can check. A property test over random coin sets catches the slice and bound bugs that unit tests on two examples miss.

Trade-offs

The general pattern is the one dynamic programming teaches: the table is a definition, not an obligation. Once the definition is right and tested, the structure of the coins, a period, a residue graph or a recurrence, decides how much of it you actually need to compute. The finite-stock case is a cousin of the bounded knapsack, and why greedy is sometimes enough is explored in greedy algorithms.

What to do next

1. Implement the plain table first and keep it in the test suite as the oracle.
2. If you dispense physical items, switch to the bounded DP and plan the whole dispense before actuating anything.
3. For large amounts, compute the pigeonhole bound from your real coin set and confirm the reduced table size.
4. For yes-or-no questions, precompute the residue distances once and answer each query with one comparison.
5. For counting, fix the modulus in the interface and check Bostan-Mori against the table for every N up to a few hundred.
6. Add a randomised property test that compares every fast path with the table on small inputs.