The Coin Change Problem in Python: Where Greedy Fails and DP Wins

Give someone coins worth 1, 3 and 4 and ask them to make 6 with as few coins as possible. Almost everyone reaches for the same strategy: take the biggest coin that fits, then repeat. That gives 4 + 1 + 1, three coins. The right answer is 3 + 3, two coins. The obvious strategy is wrong, and it is wrong on an input small enough to check in your head.

That gap is why coin change is the standard teaching case for dynamic programming. It is also two problems wearing the same clothes. Fewest coins asks for the smallest number of coins adding up to an amount. Counting ways asks how many distinct combinations add up to it at all. Both fill a single array from 0 up to the amount in O(amount × coins), and the second hides a loop-ordering bug that changes the answer from 4 to 9 without raising anything.

Greedy is not merely lucky on real money, either. It is provably correct on the coins in your pocket and provably wrong the moment you change the denominations, and telling those cases apart has a surprisingly neat answer.

Why greedy fails

Greedy here means one rule: always take the largest coin that still fits, and never reconsider.

from __future__ import annotations


def greedy_change(coins: list[int], amount: int) -> list[int] | None:
    """Take the largest coin that still fits, over and over.

    Returns the coins it picked, or None when this strategy strands itself
    with a remainder that no coin can cover.
    """
    chosen: list[int] = []
    remaining = amount

    for coin in sorted(coins, reverse=True):
        while remaining >= coin:
            chosen.append(coin)
            remaining -= coin

    return chosen if remaining == 0 else None


print("1/5/10/25 makes 63:", greedy_change([1, 5, 10, 25], 63))
print("1/3/4 makes 6:", greedy_change([1, 3, 4], 6))
print("1/5/10/20/25/50 makes 40:", greedy_change([1, 5, 10, 20, 25, 50], 40))
print("3/4 makes 6:", greedy_change([3, 4], 6))

1/5/10/25 makes 63: [25, 25, 10, 1, 1, 1]
1/3/4 makes 6: [4, 1, 1]
1/5/10/20/25/50 makes 40: [25, 10, 5]
3/4 makes 6: None

The from __future__ import annotations line is only there so the list[int] | None hints work on Python 3.9 as well as 3.10 and later. It has no effect on the algorithm.

Four lines, four lessons. The first is greedy at its best: 63 cents from US denominations genuinely needs six coins, and greedy finds them. The second is the failure at the top of this post. The third is historical — the US Mint struck a twenty-cent piece from 1875 to 1878, and with that coin in circulation greedy pays 40 cents as 25 + 10 + 5 when 20 + 20 would do. The fourth is worse than suboptimal: given only 3s and 4s, greedy grabs a 4, is left holding 2, and reports failure, even though 3 + 3 is sitting right there.

The reason fits in one sentence. Greedy commits to a coin before it knows what the remainder will cost. Taking the 4 leaves 2, payable only with two 1s. Taking a 3 leaves 3, a single coin. Choosing correctly at the top needs the price of the remainder, and that is a smaller copy of the same problem.

The idea

Write best(a) for the fewest coins that add up to exactly a. Two facts define it completely.

The base case. best(0) is 0. Making nothing takes no coins.

The recurrence. Any solution for a contains some coin — call it c. Remove it and what is left is a solution for a - c, and it must be an optimal one, because a cheaper solution for a - c could be swapped in to beat your original. So:

best(a) = 1 + the minimum of best(a - c) over every coin c that is at most a.

You never have to guess which coin goes first. You try all of them and let the already-computed answers decide. If no coin fits, or every branch is impossible, then a is impossible.

That property — an optimal answer built from optimal answers to smaller versions of the same question — is optimal substructure, the first of the two things dynamic programming needs. The second is overlapping subproblems: the same smaller question keeps coming back.

best(6) needs best(5), best(3) and best(2). But best(3) needs best(2) as well, and best(5) reaches it too further down. A plain recursion rebuilds that whole subtree every time it meets it, and the answer never changes, so computing it once is pure profit.

Memoisation keeps the recursion and caches results. Tabulation drops the recursion and fills an array from best(0) upwards, so by the time you compute best(a) everything it could read is already there. Tabulation wins here: a double loop with no recursion depth to exhaust.

Watching it work

Coins 1, 3 and 4. Amount 6. Fill the table left to right, and at every entry try every coin that fits.

• best[0] = 0. The base case.
• best[1]. Only the 1 fits: 1 + best[0] = 1.
• best[2]. Only the 1 fits: 1 + best[1] = 2.
• best[3]. Coin 1 gives 1 + best[2] = 3. Coin 3 gives 1 + best[0] = 1. Take 1.
• best[4]. Coin 1 gives 1 + best[3] = 2. Coin 3 gives 1 + best[1] = 2. Coin 4 gives 1 + best[0] = 1. Take 1.
• best[5]. Coin 1 gives 1 + best[4] = 2. Coin 3 gives 1 + best[2] = 3. Coin 4 gives 1 + best[1] = 2. Take 2.
• best[6]. Coin 1 gives 1 + best[5] = 3. Coin 3 gives 1 + best[3] = 2. Coin 4 gives 1 + best[2] = 3. Take 2.

Look at best[6]. The coin-4 branch costs 3, which is exactly greedy's answer. The table did not avoid greedy's choice — it priced it alongside the other two and picked the cheapest. That is the whole difference: greedy evaluates one option, dynamic programming evaluates all of them for the same asymptotic cost. As a bonus, the table answers every amount below 6 for free.

The code

The recurrence translated straight into two loops.

def min_coins_table(coins: list[int], amount: int) -> list[int]:
    """best[a] = fewest coins adding up to exactly a, for every a up to amount.

    `amount + 1` stands in for "impossible". Every coin is worth at least 1,
    so a real answer can never need more than `amount` coins, which makes
    `amount + 1` a value no genuine solution can ever reach.
    """
    unreachable = amount + 1
    best = [0] + [unreachable] * amount

    for target in range(1, amount + 1):
        for coin in coins:
            if coin <= target:
                # Spend this coin now, then pay for what is left with the
                # answer already computed for the smaller amount.
                best[target] = min(best[target], best[target - coin] + 1)

    return best


def min_coins(coins: list[int], amount: int) -> int:
    """Fewest coins that make `amount` exactly, or -1 if no set of coins does."""
    best = min_coins_table(coins, amount)
    return -1 if best[amount] > amount else best[amount]


table = min_coins_table([1, 3, 4], 6)
print("amount:", " ".join(f"{a:>2}" for a in range(7)))
print("best  :", " ".join(f"{v:>2}" for v in table))
print("1/3/4 makes 6 in", min_coins([1, 3, 4], 6), "coins")
print("1/5/10/25 makes 63 in", min_coins([1, 5, 10, 25], 63), "coins")
print("3/4 makes 6 in", min_coins([3, 4], 6), "coins")
print("2 makes 3 in", min_coins([2], 3), "coins")

amount:  0  1  2  3  4  5  6
best  :  0  1  2  1  1  2  2
1/3/4 makes 6 in 2 coins
1/5/10/25 makes 63 in 6 coins
3/4 makes 6 in 2 coins
2 makes 3 in -1 coins

That row of numbers is the hand trace above, produced by the code rather than by me.

A count is often not enough — you want the coins. One extra array records which coin gave each amount the answer it currently holds, and then you walk backwards.

def coins_used(coins: list[int], amount: int) -> list[int] | None:
    """One optimal set of coins for `amount`, or None if it cannot be made."""
    unreachable = amount + 1
    best = [0] + [unreachable] * amount
    # last[a] is the coin that produced the current best answer for a, which
    # is all you need to walk a full solution back out of the table.
    last = [0] * (amount + 1)

    for target in range(1, amount + 1):
        for coin in coins:
            if coin <= target and best[target - coin] + 1 < best[target]:
                best[target] = best[target - coin] + 1
                last[target] = coin

    if best[amount] == unreachable:
        return None

    chosen: list[int] = []
    remaining = amount
    while remaining > 0:
        chosen.append(last[remaining])
        remaining -= last[remaining]

    return chosen


print(coins_used([1, 3, 4], 6))
print(coins_used([1, 5, 10, 25], 63))
print(coins_used([1, 5, 10, 20, 25, 50], 40))
print(coins_used([3, 4], 6))
print(coins_used([2], 3))

[3, 3]
[1, 1, 1, 10, 25, 25]
[20, 20]
[3, 3]
None

The walk starts at the full amount and steps down, so the coins come out in whatever order the table chose them — sort the result if presentation matters. Look at the 40-cent line: with a twenty-cent piece available the table returns two coins where greedy returned three.

How the code maps to the idea

The table has amount + 1 entries, not amount, because amount 0 is a real entry and it holds the base case. This off-by-one is the most common way the code goes wrong.

The sentinel is amount + 1, deliberately. It must always lose a min against any genuine answer, and it must never look like a plausible result. Since every coin is worth at least 1, no honest solution uses more than amount coins, so amount + 1 is safely out of range. When an unreachable entry is read, best[target - coin] + 1 becomes amount + 2, the min throws it away, and impossibility propagates instead of leaking a wrong number.

The outer loop must ascend. Computing best[target] reads best[target - coin], and target - coin is strictly smaller because every coin is positive, so ascending order guarantees that value is already final. Every tabulated DP comes down to this one question: in what order can I fill the table so nothing is read before it is written?

The coin <= target guard is the "every coin at most a" clause of the recurrence, and it keeps the index non-negative.

Edge cases fall out of the arithmetic. Amount 0 returns 0 because the loop body never runs. An impossible amount returns -1 because the sentinel survives. Duplicate denominations cost redundant work but nothing else, and coins bigger than the amount never pass the guard. The one real assumption is that every coin is a positive integer; a zero or negative denomination breaks the ascending-order argument and the code with it.

The same recurrence written top-down is often the version you would sketch first in an interview.

from functools import lru_cache


def min_coins_memo(coins: tuple[int, ...], amount: int) -> int:
    """The same recurrence written top-down, with a cache doing the work."""

    @lru_cache(maxsize=None)
    def best(remaining: int) -> float:
        if remaining == 0:
            return 0
        # default=inf covers "no coin fits". Infinity propagates upwards and
        # can never win a min(), which is exactly what "impossible" should do.
        return 1 + min(
            (best(remaining - coin) for coin in coins if coin <= remaining),
            default=float("inf"),
        )

    answer = best(amount)
    return -1 if answer == float("inf") else int(answer)


print(min_coins_memo((1, 3, 4), 6),
      min_coins_memo((1, 5, 10, 25), 63),
      min_coins_memo((2,), 3))

2 6 -1

Same answers, with functools.lru_cache (or functools.cache, the same thing without a size limit, added in Python 3.9) doing the bookkeeping. Two caveats. The coins must be a tuple, because cached arguments have to be hashable and a list is not. And with a 1-coin in the set the recursion goes amount levels deep, so this version raises RecursionError somewhere above an amount of about 1,000, while the table version handles a million.

The second question: how many ways?

Same coins, same amount, different question: how many distinct combinations of 1s, 3s and 4s add up to 6? Order must not matter — 1 + 1 + 4 and 4 + 1 + 1 are the same handful of coins.

Brute force settles what the answer should be. Enumerating every non-decreasing sequence counts each multiset exactly once.

def all_combinations(coins: list[int], amount: int) -> list[tuple[int, ...]]:
    """Every non-decreasing multiset of coins summing to `amount`, brute force."""
    ordered = sorted(coins)
    found: list[tuple[int, ...]] = []

    def build(start: int, remaining: int, chosen: tuple[int, ...]) -> None:
        if remaining == 0:
            found.append(chosen)
            return
        for index in range(start, len(ordered)):
            coin = ordered[index]
            if coin <= remaining:
                # `index`, not `index + 1`: coins are unlimited, so the same
                # denomination can be picked again. Never stepping backwards
                # is what stops 1+3 and 3+1 counting as two different answers.
                build(index, remaining - coin, chosen + (coin,))

    build(0, amount, ())
    return found


for combination in all_combinations([1, 3, 4], 6):
    print(combination)

(1, 1, 1, 1, 1, 1)
(1, 1, 1, 3)
(1, 1, 4)
(3, 3)

Four ways, and the shortest has two coins — the answer to the first problem. The two questions really are reading different things off the same set of solutions.

Enumerating does not scale: with a fixed set of denominations the number of combinations grows polynomially in the amount, and there is no reason to build them all just to count them. The counting table looks almost identical to the minimising one, with one loop swapped.

def count_combinations(coins: list[int], amount: int) -> int:
    """How many distinct multisets of coins add up to exactly `amount`."""
    ways = [1] + [0] * amount

    for coin in coins:                        # denominations on the outside
        for target in range(coin, amount + 1):
            ways[target] += ways[target - coin]

    return ways[amount]


def count_orderings(coins: list[int], amount: int) -> int:
    """The same two loops, swapped. This counts ordered sequences instead."""
    ways = [1] + [0] * amount

    for target in range(1, amount + 1):       # amounts on the outside
        for coin in coins:
            if coin <= target:
                ways[target] += ways[target - coin]

    return ways[amount]


print("combinations:", count_combinations([1, 3, 4], 6))
print("orderings   :", count_orderings([1, 3, 4], 6))
print("ways to make 100 from 1/5/10/25:", count_combinations([1, 5, 10, 25], 100))

combinations: 4
orderings   : 9
ways to make 100 from 1/5/10/25: 242

Why the coin loop has to be on the outside

The two functions differ by nothing but loop order and disagree by more than a factor of two. Here is what each one actually computes.

With coins on the outside, the array carries an invariant that holds after every complete pass: ways[a] is the number of ways to make a using only the denominations processed so far. Each pass folds in exactly one new denomination. A combination either uses zero copies of that coin, in which case it was already counted, or at least one, in which case removing one copy leaves a combination for a - coin drawn from the same coin set — which is precisely what ways[a - coin] holds at that moment, because the inner loop ascends and has already updated it during this pass. Every combination is counted once, in the pass belonging to its largest denomination.

With amounts on the outside, that invariant is gone. ways[a] becomes "ways to reach a by adding one coin at a time to a smaller total", and the same coins form a different route depending on the order you add them. Making 4 counts as 1+1+1+1, 1+3, 3+1 and 4 — four ordered sequences where there are only three combinations.

Printing the array after each pass makes the invariant visible.

ways = [1] + [0] * 6
print("start       :", ways)
for coin in [1, 3, 4]:
    for target in range(coin, 7):
        ways[target] += ways[target - coin]
    print(f"after coin {coin}:", ways)

start       : [1, 0, 0, 0, 0, 0, 0]
after coin 1: [1, 1, 1, 1, 1, 1, 1]
after coin 3: [1, 1, 1, 2, 2, 2, 3]
after coin 4: [1, 1, 1, 2, 3, 3, 4]

Read the rows. After the 1-coin every amount has exactly one way, all 1s. After the 3-coin, amount 6 reads 3: the all-1s way, plus the 2 ways of making 3 from 1s and 3s with a 3 added on top. After the 4-coin it reads 4: the 3 ways that avoid the 4-coin entirely, plus the single way to make the remaining 2.

Rather than trust one hand-checked example, machine-check the table against the enumerator across a hundred amounts.

disagreements = [
    amount
    for amount in range(100)
    if len(all_combinations([1, 3, 4], amount)) != count_combinations([1, 3, 4], amount)
]
print("amounts where brute force and the DP disagree:", disagreements)

amounts where brute force and the DP disagree: []

Complexity

Time: O(amount × coins), for both problems. Count the minimising version directly. The outer loop body runs once per target from 1 to amount, so amount times. Inside it, the loop runs once per denomination, so c times for c coins. That inner body is one comparison, one subtraction, one addition and one min — all constant time. Total: exactly amount × c constant-time steps. Making 63 cents from four US denominations is 252 steps.

The counting version has the loops the other way round but the same product. Its inner loop runs amount - coin + 1 times, and summing that over all c coins gives at most amount × c. Slightly fewer steps, same bound.

Space: O(amount). One array of amount + 1 integers; reconstruction adds a second of the same length, still O(amount). If you only need best[amount] and the largest coin is small, a ring buffer of that size is enough, since the recurrence never reaches back further than the largest coin.

Without the table, it is exponential. The uncached recursion re-explores the same subproblems endlessly, and its call count follows its own recurrence: one call for the node, plus a whole call tree for every coin that fits.

def naive_call_count(coins: list[int], amount: int) -> int:
    """How many calls the uncached recursion makes before it has the answer."""
    calls = [1] * (amount + 1)
    for target in range(1, amount + 1):
        calls[target] = 1 + sum(
            calls[target - coin] for coin in coins if coin <= target
        )
    return calls[amount]


for amount in (10, 20, 30, 40):
    naive = naive_call_count([1, 3, 4], amount)
    print(f"amount {amount:>2}: {naive:>13,} naive calls vs {amount * 3:>3} table updates")

amount 10:           168 naive calls vs  30 table updates
amount 20:        20,736 naive calls vs  60 table updates
amount 30:     2,550,408 naive calls vs  90 table updates
amount 40:   313,679,521 naive calls vs 120 table updates

The call count multiplies by roughly 123 every ten units of amount — about 1.6 per unit — while the table grows by 30 updates. That is the value proposition of dynamic programming in four lines.

The honest caveat: O(amount × coins) is pseudo-polynomial, not polynomial. The input's size is the number of coins plus the number of digits in the amount. One billion is ten digits, but the table needs a billion entries. Measured against input length the algorithm is exponential, and that is not a technicality: change-making is genuinely NP-hard, which Lueker proved in 1975 by reduction from subset sum. The DP is fast whenever the amount is small enough to allocate an array for, and useless otherwise.

It is the unbounded knapsack problem. Map each coin to an item whose weight is the coin's value and whose value is 1, set the capacity to the amount, and "fewest coins for exactly this amount" becomes "minimum total value at exactly this weight" with unlimited copies of each item. The contrast with 0/1 knapsack is worth pinning down, because it comes down to loop direction: there each item is used at most once and the inner amount loop runs downwards, so a decision only ever reads cells this item has not touched. Here coins are unlimited and the inner loop runs upwards, so a decision can read a cell this same coin already updated. Up means reuse, down means once.

When greedy is actually safe

A coin system where greedy always returns an optimal answer is called canonical. The US set 1, 5, 10, 25 is canonical, and so is the euro coin set 1, 2, 5, 10, 20, 50. That is not luck: modern currencies follow a 1-2-5 pattern precisely so people can make change by instinct.

Canonicity cannot be eyeballed, though. The set 1, 7, 10 looks perfectly sensible and breaks at 14, where greedy pays 10 + 1 + 1 + 1 + 1 and the answer is 7 + 7. Add a twenty-cent piece to the US set and it breaks at 40. There is no visual pattern to spot.

You can settle it mechanically, thanks to a lovely result: Kozen and Zaks proved in 1994 that if a coin system is not canonical, its smallest counterexample is below the sum of its two largest coins. An infinite question becomes a finite one.

def smallest_greedy_failure(coins: list[int]) -> int | None:
    """The smallest amount where greedy is not optimal, or None if there is none.

    Kozen and Zaks proved in 1994 that if a system is not canonical, its
    smallest counterexample is below the sum of its two largest coins. That
    turns an infinite question into a finite one.
    """
    ordered = sorted(coins)
    if len(ordered) < 2 or ordered[0] != 1:
        raise ValueError("needs at least two denominations, the smallest being 1")

    limit = ordered[-1] + ordered[-2]
    best = min_coins_table(ordered, limit)

    for amount in range(1, limit + 1):
        greedy = greedy_change(ordered, amount)
        if greedy is None or len(greedy) > best[amount]:
            return amount

    return None


for system in ([1, 5, 10, 25], [1, 2, 5, 10, 20, 50],
               [1, 5, 10, 20, 25, 50], [1, 3, 4], [1, 7, 10]):
    print(f"{str(system):<24} first greedy failure: {smallest_greedy_failure(system)}")

[1, 5, 10, 25]           first greedy failure: None
[1, 2, 5, 10, 20, 50]    first greedy failure: None
[1, 5, 10, 20, 25, 50]   first greedy failure: 40
[1, 3, 4]                first greedy failure: 6
[1, 7, 10]               first greedy failure: 14

That check is itself pseudo-polynomial, since it builds a table up to the sum of the two largest coins. For very large denominations you would want David Pearson's 2005 algorithm, which decides canonicity in O(c³) time in the number of denominations alone. Either way the advice is the same: if you intend to ship greedy, run the check in a unit test so the build breaks when somebody adds a denomination.

One more caveat catches real systems. Canonicity assumes an unlimited supply of every coin. If the till has run out of 10s then 30 must be paid as 25 + 5, and greedy's guarantee evaporates even for the US set. Limited supplies make it the bounded coin change problem, which needs an extra table dimension or a per-coin capacity loop.

When to use it, and when not to

Use the fewest-coins table when the denominations are arbitrary, user-supplied or unverified; when you need the coins and not just a count; or when you need many amounts at once, since one table answers all of them.

Use greedy when the system is canonical, you have verified that mechanically, and supply is unlimited. It costs O(c log c) to sort plus one step per coin dispensed, needs no array, and is the right answer for a cash register in a country with a sane currency.

Do not use this DP when the amount is enormous. At a billion the table is the problem, not the loops. If the system is canonical, use greedy; if it is not, the problem is genuinely hard and the answer is an integer-programming solver, not a bigger array.

Do not use the counting table to enumerate. Counting is cheap, listing is not. If you need the actual combinations, use the recursive enumerator above and stream them.

Never run any of this on floating-point money. 0.1 + 0.2 is not 0.3 in binary floating point, and a table indexed by cents derived from floats will disagree with itself. Work in the smallest unit as integers — pence, cents, satoshis — end to end.

Where it shows up in the real world

Change-making machines and self-checkout coin hoppers. A machine dispensing change wants to use as few coins as possible so the hoppers last longer between refills, and it must work with whatever denominations are actually loaded. Because a hopper can run dry, this is the bounded version — the "exact change only" light on a vending machine is precisely this problem reporting that it has no solution.

Cash dispensers. An ATM holds a small number of note cassettes, each with a fixed denomination and a finite count, and has to satisfy a withdrawal from what it has. That is bounded coin change with the denominations decided by whoever loaded the machine.

Assembling a payment from what you hold. Paying an exact amount from a set of notes, gift-card balances or UTXOs is the same question with the same two variants: can it be done at all, and with the fewest pieces.

Which amounts are impossible at all. The table's -1 entries answer a separate classical question — the Frobenius coin problem. The best-known instance is the McNugget numbers, from the days when Chicken McNuggets came in boxes of 6, 9 and 20.

impossible = [amount for amount in range(1, 61) if min_coins([6, 9, 20], amount) == -1]
print("cannot be bought exactly:", impossible)

cannot be bought exactly: [1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43]

43 is the largest, and the list proves why nothing above it can appear: 44, 45, 46, 47, 48 and 49 are all buyable, and every larger number is one of those six plus some multiple of 6.

Teaching. This is the standard example for greedy versus dynamic programming, and the counting variant is the "counting change" problem from section 1.2.2 of Structure and Interpretation of Computer Programs, whose answer for a dollar in 1, 5, 10, 25 and 50 cent coins is 292 — the 242 printed earlier is the same count without the half dollar.

Common mistakes

Shipping greedy on an unverified coin system. The failure is silent: correct answers on every amount you happened to test, wrong ones in production. Run smallest_greedy_failure in a test and assert it returns None.

Swapping the loops in the counting version. Coins outside gives combinations; amounts outside gives ordered sequences. Both compile, neither warns, and the numbers differ by a lot. If the question says "how many ways", it almost always means combinations.

Iterating the inner loop downwards. That is the 0/1 knapsack pattern, and it limits every coin to one use. For unlimited coins the inner loop must ascend.

Using -1 as the "impossible" marker inside the table. Then best[target - coin] + 1 is 0, which looks like a fantastic answer and wins every min. Use a sentinel that can only lose, such as amount + 1 or float("inf"), and convert to -1 only on the way out.

Sizing the table amount instead of amount + 1. Amount 0 is a real entry and the base case lives in it.

Answering the wrong question. "Coin change" names both problems. Before writing a line, decide whether you are asked for the fewest coins or the number of ways.

Practice

1. Change coins_used to return a dictionary mapping each denomination to how many of it were used, instead of a flat list.
2. Find the largest amount that cannot be made from coins worth 6, 9 and 20 by scanning the table, without hard-coding 43.
3. Solve the bounded version: given a limited count of each denomination, find the fewest coins that make an amount.
4. Count combinations that use at most k coins in total, which needs a two-dimensional table indexed by amount and coin count.
5. Search all coin systems of the form 1, a, b with a below b below 20 and report which ones are canonical.

Summary

Coin change is where greedy stops being good enough and you can see exactly why: greedy picks a coin before it knows the price of the remainder, and the table computes that price first. Both variants are the same array filled from 0 upwards for O(amount × coins) — the minimising one takes a min over coins, the counting one takes a sum, and the counting one only counts combinations if the coin loop is on the outside.

Learn the fewest-coins table first, then the counting table, then the loop-order argument that separates them. Together they cover most of what unbounded dynamic programming ever asks of you, and the canonicity result is a rare case where "is my greedy heuristic actually correct" has a clean, checkable answer.

Keep reading

• Dynamic Programming Explained — memoisation versus tabulation, and how to recognise a DP problem before you have solved it.
• The 0/1 Knapsack Problem — the same table with each item used at most once, which is why its inner loop runs the other way.
• Greedy Algorithms Explained — when taking the best option now is provably right, and the exchange argument that proves it.
• Big O Notation — including what pseudo-polynomial really means.