Tabulate Minimum Coin Count

Practice Exercise Intermediate Medium Tabulation Array

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement minimum_coin_count(coins, amount). Coins may be reused. Return the fewest coins totaling amount, or -1 when impossible. amount is nonnegative and coins are positive.

Starter code

def minimum_coin_count(coins, amount):
    pass

Test cases

reusable-coins

{
  "args": [
    [
      1,
      3,
      4
    ],
    6
  ]
}

Expected: 2

impossible-amount

{
  "args": [
    [
      2,
      4
    ],
    7
  ]
}

Expected: -1

Wizard outline

Step 1: Seed the zero amount
Create a table with zero solved and all other states impossible. Every combination grows from the empty total using one additional coin.
Step 2: Fill reachable totals
Build each amount from already solved smaller totals. For a final coin c, the best solution is one plus the best solution for current-c.
Step 3: Translate impossible states
Return -1 when the target sentinel was never improved. The table sentinel is an internal implementation detail, not the public result.

Footguns and prerequisites

Initializing unknown states to zero makes impossible amounts look solved.
Iterating only coin values without amount states can accidentally enforce one-use coins.
dynamic programming

Reviewed references

Python More on Lists

Recommended approach and implementation

Tabulate the fewest coins for every amount from zero upward and translate the unresolved sentinel to -1.

Why it works: For each amount, every valid final coin points to a smaller already-correct state. Taking the minimum over all final coins therefore yields the optimal count, while an unchanged sentinel means no composition exists.

def minimum_coin_count(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current:
                dp[current] = min(dp[current], dp[current - coin] + 1)
    return -1 if dp[amount] > amount else dp[amount]