Coin Change

Find the fewest coins needed to make an amount.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Coin Change: For each amount, minimize one plus every already-solved predecessor amount.

Input and goalFind the fewest coins needed to make an amount.

Initialize the DP rowfewest[0]=0 and amounts 1 through 7 use sentinel 8, meaning unreachable.

total=00081828384858687

examplecoins = [2, 3], amount = 7; unreachable = 8indexMeaningamountfewest[0,8,8,8,8,8,8,8]

Recognize it

The target can be composed repeatedly from reusable coin values and asks for a minimum count, so each total depends on smaller totals.

Keep true

When processing total t, every fewest[x] for x<t is final; after trying each valid coin, fewest[t] is the minimum candidate examined so far.

Reuse it

Define the answer for one total from already-solved smaller totals and aggregate with min; this transfers to minimum steps, perfect squares, and shortest composition problems.

Pattern: One-dimensional DP.

State: fewest[total] is the fewest coins needed for total.

Simple idea: To finish total with one coin, look at the answer for total - coin and add one.

def coin_change(coins: list[int], amount: int) -> int:
   unreachable = amount + 1
   fewest = [0] + [unreachable] * amount

   for total in range(1, amount + 1):
      for coin in coins:
         if 0 < coin <= total:
            fewest[total] = min(fewest[total], 1 + fewest[total - coin])

   return fewest[amount] if fewest[amount] != unreachable else -1

Cost: $O(amount\times coins)$ time and $O(amount)$ space.