Module 23 · Dynamic Programming I: One-Dimensional State

228. Minimum Coin Change

Interview · Download this solution · All solutions and shared helpers

Problem

Given positive integer coin denominations and a nonnegative amount, return the minimum number of coins summing exactly to that amount, with unlimited reuse. Duplicate denominations are ignored. Return -1 if unreachable and zero for amount zero. Do not mutate the inputs.

Examples

Example 1

min_coin_change([1,3,4],6)
=> 2

Two coins of value 3 beat the greedy choice.

Example 2

min_coin_change([2],3)
=> -1

No exact odd amount is reachable.

Example 3

min_coin_change([],0)
=> 0

The empty selection reaches zero.

Reveal the worked solution and reasoning

Why this mechanism works

Define dp[x] as the optimum for exact amount x. Every nonempty solution has a final coin c and an optimal solution for x-c before it; replacing a nonoptimal prefix would improve the whole solution. Positive coins ensure the predecessor amount is smaller, so ascending amounts form a valid computation order.

State and boundaries

dp[0]=0; an infinity sentinel marks amounts not yet known reachable. At amount x, every dp[x-c] read is already complete.

Protocol

Deduplicate positive coins.
Initialize exact-amount states to infinity except zero.
Scan amounts upward.
For every fitting coin minimize dp[x] with dp[x-coin]+1.
Convert an unreachable final state to -1.

Visualization

coins [1,3,4], amount 6
greedy 4+1+1 uses 3 coins
dp[6] can extend dp[3]=1 with coin 3 -> 2 coins

Python implementation

def min_coin_change(coins, amount):
    values = set(coins)
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for total in range(1, amount + 1):
        for coin in values:
            if coin <= total:
                dp[total] = min(dp[total], dp[total - coin] + 1)
    return -1 if dp[amount] == float('inf') else dp[amount]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

min_coin_change([1,3,4],6)

L2 min_coin_change: values = set(coins)
coins=[1, 3, 4]; amount=6; values={1, 3, 4}

L3 min_coin_change: dp = [float('inf')] * (amount + 1)
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[inf, inf, inf, inf, inf, inf, inf]

L4 min_coin_change: dp[0] = 0
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, inf, inf, inf, inf, inf, inf]

L5 min_coin_change: for total in range(1, amount + 1):
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, inf, inf, inf, inf, inf, inf]; total=1

L6 min_coin_change: for coin in values:
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, inf, inf, inf, inf, inf, inf]; total=1; coin=1

L8 min_coin_change: dp[total] = min(dp[total], dp[total - coin] + 1)
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, 1, inf, inf, inf, inf, inf]; total=1; coin=1

L6 min_coin_change: for coin in values:
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, 1, inf, inf, inf, inf, inf]; total=1; coin=3

L6 min_coin_change: for coin in values:
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, 1, inf, inf, inf, inf, inf]; total=1; coin=4

... 24 intermediate state changes omitted ...

L8 min_coin_change: dp[total] = min(dp[total], dp[total - coin] + 1)
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, 1, 2, 1, 1, 2, 3]; total=6; coin=1

L6 min_coin_change: for coin in values:
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, 1, 2, 1, 1, 2, 3]; total=6; coin=3

L8 min_coin_change: dp[total] = min(dp[total], dp[total - coin] + 1)
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, 1, 2, 1, 1, 2, 2]; total=6; coin=3

L6 min_coin_change: for coin in values:
coins=[1, 3, 4]; amount=6; values={1, 3, 4}; dp=[0, 1, 2, 1, 1, 2, 2]; total=6; coin=4

Result: 2. Two coins of value 3 beat the greedy choice.

min_coin_change([2],3)

L2 min_coin_change: values = set(coins)
coins=[2]; amount=3; values={2}

L3 min_coin_change: dp = [float('inf')] * (amount + 1)
coins=[2]; amount=3; values={2}; dp=[inf, inf, inf, inf]

L4 min_coin_change: dp[0] = 0
coins=[2]; amount=3; values={2}; dp=[0, inf, inf, inf]

L5 min_coin_change: for total in range(1, amount + 1):
coins=[2]; amount=3; values={2}; dp=[0, inf, inf, inf]; total=1

L6 min_coin_change: for coin in values:
coins=[2]; amount=3; values={2}; dp=[0, inf, inf, inf]; total=1; coin=2

L5 min_coin_change: for total in range(1, amount + 1):
coins=[2]; amount=3; values={2}; dp=[0, inf, inf, inf]; total=2; coin=2

L8 min_coin_change: dp[total] = min(dp[total], dp[total - coin] + 1)
coins=[2]; amount=3; values={2}; dp=[0, inf, 1, inf]; total=2; coin=2

L5 min_coin_change: for total in range(1, amount + 1):
coins=[2]; amount=3; values={2}; dp=[0, inf, 1, inf]; total=3; coin=2

Result: -1. No exact odd amount is reachable.

Why the solution is correct

Each candidate corresponds to a legal last coin appended to an exact smaller amount. Every legal solution has such a last coin, so minimizing across them considers an optimum. The base represents taking no coins, and positive denominations guarantee acyclic dependencies.

Time and space

O(A*C) transition time and O(A+C) storage for amount A and C distinct denominations, plus denomination-set construction. This is pseudopolynomial in the numeric amount.

Common mistakes

A greedy largest-coin choice fails for arbitrary denominations, such as [1,3,4] at amount 6. Zero coins break the smaller-state rationale.

Reasoning card

State: dp[0]=0; an infinity sentinel marks amounts not yet known reachable. At amount x, every dp[x-c] read is already complete.

Invariant: dp[x] is the minimum coins required for exactly x.

Decision to rehearse: Build exact-amount answers from smaller amounts.

Finish: Convert an unreachable final state to -1

Transfer exercise

Store the last coin chosen for each reachable amount to reconstruct one minimum-coin combination.