Minimum coins with a witness

The baseline recursively tries each final coin and takes the best result. It recomputes the same remaining amounts across many paths, potentially exponentially. Greedy avoids that search but lacks a proof for arbitrary denominations; the worked example is enough to reject it for this contract.

Define best[a] as the minimum number of coins summing exactly to a. Set best[0]=0 and other entries to a sentinel larger than any feasible count. For each subtotal a and coin c≤a, consider best[a-c]+1. Save both the improving count and last coin. Fill amounts upward because every dependency a-c is strictly smaller than a.

before processing a, all smaller amounts have optimal counts. Every nonempty solution for a has some last coin c; deleting it leaves a solution for a-c, which cannot beat best[a-c]. Conversely appending c to a reachable best subproblem constructs a valid candidate. Taking the minimum is therefore optimal.

Reconstruction repeatedly subtracts the stored last coin until zero. With m supplied coins, k unique coins, and amount A, time is O(m + k log k + A(k+1)), auxiliary space O(A+k), and witness space O(M) for M returned coins. This is pseudopolynomial: A can be much larger than the number of digits encoding it. O(A) allocation is not acceptable for every arbitrarily large numeric input even though the recurrence is correct.

Follow-up 1 — one coin of each type. Predict amount 6 with [1,3,4]: impossible. Update a one-dimensional table in descending amount order for each coin so the current coin cannot feed another update in the same pass. Alternatively add an inventory-position dimension and reconstruct with that state.

Follow-up 2 — each coin has a handling cost. Replace +1 with that coin's cost and define whether the output minimizes cost alone or uses count as a tie-breaker. The amount dependency remains acyclic for positive denominations. Negative-sized coins would destroy that ordering and need a different problem model.

Senior depth derives rather than memorizes the state, verifies a witness, and explains unreachable sentinels. Lead depth adds amount budgets and input contracts.

Reference: solution.py (download file, source below); tests use an independent BFS over amounts and check optimal count, witness sum, impossible amounts, and invalid coins.

"""Minimum unbounded coin count with one optimal witness."""


def minimum_coins(coins, amount):
    if not isinstance(amount, int) or amount < 0:
        raise ValueError("nonnegative integer amount required")
    unique = set()
    for coin in coins:
        if not isinstance(coin, int) or coin <= 0:
            raise ValueError("positive integer coins required")
        unique.add(coin)
    coins = sorted(unique)
    unreachable = amount + 1
    best = [0] + [unreachable] * amount
    last = [None] * (amount + 1)
    for subtotal in range(1, amount + 1):
        for coin in coins:
            if coin > subtotal:
                break
            candidate = best[subtotal - coin] + 1
            if candidate < best[subtotal]:
                best[subtotal], last[subtotal] = candidate, coin
    if best[amount] == unreachable:
        return -1, []
    used = []
    remaining = amount
    while remaining:
        used.append(last[remaining])
        remaining -= last[remaining]
    return best[amount], used

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/33-coin-change -p 'test_*.py'