LESSON 113 · DEEPER PYTHON30 min

Solve Coin Change with Dynamic Programming

Return the minimum number of positive-denomination coins for a target amount, or None if unreachable.

Before you start: Lists · Loops · Conditions

Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons

WATCH

Video lesson: Solve Coin Change with Dynamic Programming

The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube

Jump to a chapter

Read the video transcript

Select a timestamp to watch that moment on YouTube.

00:00
For six units, greedy picks four plus one plus one. Run it. Can two three-unit coins beat the program's answer of three pieces? The broken result is the list four, one, one: three coins. It chose the biggest affordable coin at each step, which is a local rule. That rule works for some denomination systems but has no general proof. The input one, three, four exposes the gap immediately. Trace the greedy choices without jumping to the answer. Six is at least four, so the program takes four and leaves two. Neither three nor four fits the remainder, so it takes one twice. The printed list is four, one, one.
00:41
Now compare three plus three, which pays the same amount with two coins. A counterexample this small is more useful than timing the code: the implementation is fast at solving the wrong optimization rule for these denominations. We can state the failed assumption precisely: a locally best first coin is not always part of a globally shortest combination. Greedy never revisits the decision to take four. A dynamic program does revisit the possibility indirectly by comparing all legal last coins for every target. A unit coin guarantees this particular example can make every nonnegative amount,
01:21
but the general function must still handle a coin set without one. The diagnosis prints greedy count three and the better pair three, three with count two. Dynamic programming compares all allowed final coins for each smaller amount. For amount six, a final three leaves amount three, already solved with one coin, so that candidate needs two total. Work the table from zero to six for coins one, three, and four. The minimum counts are zero, one, two, one, one, two, two. At amount six, using a final one leaves five with two coins, for three total. A final three leaves three with one, for two total.
02:01
A final four leaves two with two, for three total. The minimum is two. This calculation shows exactly where a local largest-coin rule loses information. The fixed function starts dp zero at zero coins and marks other amounts unreachable. For each target amount it checks positive denominations that fit and updates from reachable remainders. It prints two for target six, agreeing with the two three-unit coins. Negative targets and nonpositive coin values are rejected before indexing the table. In the source, dp at zero is the base case, not an arbitrary initialization.
02:41
Every positive amount asks which coin could be the last one used. If that coin fits and its remainder is reachable, one plus the remainder's best count is a candidate. The code keeps the smallest candidate. Processing amounts in ascending order ensures those remainder entries are already complete. At six, the candidate through three wins and the terminal prints two. The recurrence is optimal because every valid solution for a positive amount has some final coin. Remove that coin and the remaining amount must itself use the fewest possible coins, or we could replace it with a better remainder and improve the whole solution.
03:22
Taking the minimum over every final coin therefore covers all possible optimal endings. This argument explains why the table needs earlier entries to be correct before later entries are filled. The verifier prints zero for target zero and None for an unreachable target with only two-unit coins. The table takes work proportional to target times number of denominations, so enormous target values need a different design. The algorithm minimizes piece count for the supplied coin system, not some other cost. For target zero, take no coins and return zero before considering any denomination.
04:02
With only two-unit coins, target three has no valid final coin leading to a reachable remainder, so None is clearer than an invented large number. A negative coin would undermine the ascending-table argument; validate values before the loop. The table is indexed by amount, so its memory and runtime scale with the numeric target. Do not feed it an enormous target without accounting for that cost. For only two-unit coins and amount three, the reachable table values are zero at amount zero and one at amount two; amounts one and three remain unreachable. Treating an unreachable entry as a huge finite count could accidentally leak a
04:43
nonsense answer if the sentinel is mishandled. None makes the absence of a combination explicit. If a caller also needs the actual coins, store the chosen last denomination alongside each best count. As a control case, target five with coins one, three, and four needs two coins: four plus one. Greedy happens to succeed there. A successful case does not prove its choice rule; the neighboring target six is the useful counterexample.

THE IDEA

Understand the concept

A cashier has coins worth one, three and four units. Greedy selection takes the largest affordable coin first, so for six it chooses four plus one plus one. Two three-unit coins use fewer pieces. A dynamic-programming table records the best answer for every smaller amount instead of trusting a local choice.

Greedy is correct for some coin systems but not for arbitrary denominations. The broken run reports three coins for target six even though two suffice. A program that only tests familiar currency may never reveal the assumption; the deliberately awkward denomination set is the diagnostic counterexample.

For each amount from one to the target, inspect all denominations that fit. The candidate count is one plus the best count for the remainder. Store the minimum among reachable candidates. This builds from known smaller answers, so every table entry has a reason rather than an unexplained magic value. Initialize dp[0] to zero and all other entries to an unreachable marker. For each amount, consider only positive coins not larger than that amount; if dp[amount - coin] is reachable, update dp[amount]. Return None when the target stays unreachable. Reject negative targets and nonpositive denominations before building the table.

Target zero requires zero coins. A target of three with only two-unit coins is unreachable, so return None. The final run checks both. The time and memory cost grow with target amount, which makes this approach unsuitable for enormous numeric targets without further design. This algorithm minimizes coin count, not monetary value or weight; denominations define the available moves. Production financial calculations have other constraints and should not infer optimality from a greedy shortcut without proving it for the specific coin system.

A cashier has coins worth one, three and four units.
Greedy is correct for some coin systems but not for arbitrary denominations.
Initialize dp[0] to zero and all other entries to an unreachable marker.
Target zero requires zero coins.

WORKED EXAMPLES

See it step by step

Read the code, predict the output, then compare it with the result.

01. See greedy choose three coins

PYTHON

coins=[4,3,1]; amount=6; used=[]
for coin in coins:
    while amount>=coin: used.append(coin); amount-=coin
print(used)

EXPECTED OUTPUT

[4, 1, 1]

Greedy chooses four plus two ones because it commits to four too early.

02. Compare the better combination

PYTHON

greedy=[4,1,1]; optimal=[3,3]
print(sum(greedy), len(greedy))
print(sum(optimal), len(optimal))

EXPECTED OUTPUT

6 3
6 2

Both pay six, but the second combination uses fewer coins.

03. Build small optimal states

PYTHON

dp=[0,None,None,None]
for amount in range(1,4):
    candidates=[dp[amount-c]+1 for c in (1,3) if c<=amount and dp[amount-c] is not None]
    dp[amount]=min(candidates) if candidates else None
print(dp)

EXPECTED OUTPUT

[0, 1, 2, 1]

The table stores the best known count for each amount from zero to three.

GO DEEPER

A closer look

Follow the reasoning, inspect each result, then try the suggested changes in the console below.

01 / 03

Observe the first result

A cashier has coins worth one, three and four units. Greedy selection takes the largest affordable coin first, so for six it chooses four plus one plus one. Two three-unit coins use fewer pieces. A dynamic-programming table records the best answer for every smaller amount instead of trusting a local choice.

Greedy chooses four plus two ones because it commits to four too early. For each amount from one to the target, inspect all denominations that fit. The candidate count is one plus the best count for the remainder. Store the minimum among reachable candidates. This builds from known smaller answers, so every table entry has a reason rather than an unexplained magic value.

PYTHON

coins=[4,3,1]; amount=6; used=[]
for coin in coins:
    while amount>=coin: used.append(coin); amount-=coin
print(used)

EXPECTED OUTPUT

[4, 1, 1]

Follow the reasoning

Predict the first sample's printed value and type.
Run it, then compare with the expected output.

02 / 03

Change the rule deliberately

Greedy is correct for some coin systems but not for arbitrary denominations. The broken run reports three coins for target six even though two suffice. A program that only tests familiar currency may never reveal the assumption; the deliberately awkward denomination set is the diagnostic counterexample.

Both pay six, but the second combination uses fewer coins. Initialize dp[0] to zero and all other entries to an unreachable marker. For each amount, consider only positive coins not larger than that amount; if dp[amount - coin] is reachable, update dp[amount]. Return None when the target stays unreachable. Reject negative targets and nonpositive denominations before building the table. Start dp = [None] * (amount + 1), set dp[0] = 0, then update each amount using reachable smaller states.

PYTHON

greedy=[4,1,1]; optimal=[3,3]
print(sum(greedy), len(greedy))
print(sum(optimal), len(optimal))

EXPECTED OUTPUT

6 3
6 2

Follow the reasoning

Identify the line that changes the rule.
Run the corrected sample with the same input.

03 / 03

Verify the boundary

For each amount from one to the target, inspect all denominations that fit. The candidate count is one plus the best count for the remainder. Store the minimum among reachable candidates. This builds from known smaller answers, so every table entry has a reason rather than an unexplained magic value. Initialize dp[0] to zero and all other entries to an unreachable marker. For each amount, consider only positive coins not larger than that amount; if dp[amount - coin] is reachable, update dp[amount]. Return None when the target stays unreachable. Reject negative targets and nonpositive denominations before building the table.

The table stores the best known count for each amount from zero to three. Target zero requires zero coins. A target of three with only two-unit coins is unreachable, so return None. The final run checks both. The time and memory cost grow with target amount, which makes this approach unsuitable for enormous numeric targets without further design. This algorithm minimizes coin count, not monetary value or weight; denominations define the available moves. Production financial calculations have other constraints and should not infer optimality from a greedy shortcut without proving it for the specific coin system.

PYTHON

dp=[0,None,None,None]
for amount in range(1,4):
    candidates=[dp[amount-c]+1 for c in (1,3) if c<=amount and dp[amount-c] is not None]
    dp[amount]=min(candidates) if candidates else None
print(dp)

EXPECTED OUTPUT

[0, 1, 2, 1]

Follow the reasoning

Try the documented edge case.
Explain why the output satisfies the function contract.

HANDS-ON

Try it in Python

Edit the example and run it. Python starts in your browser the first time you click Run.

Python console

Ready to run

def min_coins(coins, amount):
    count = 0
    for coin in sorted(coins, reverse=True):
        count += amount // coin
        amount %= coin
    return count if amount == 0 else None

print(min_coins([1, 3, 4], 6))

Need input()? Add one value per line

Input lines

Ctrl / ⌘ + Enter to run

OUTPUT

Your output appears here.

Your turnReplace greedy selection with a DP table. Return the minimum count, 0 for target zero, and None when no combination exists. Reject negative amount or nonpositive denominations with ValueError. The prepared call prints 2.

Need a hint?

Start dp = [None] * (amount + 1), set dp[0] = 0, then update each amount using reachable smaller states.

Complete the task and select Check task to verify your code.

DEBUG BETTER

Typical mistakes

Everyone meets these errors. See what causes them and how to fix them.

The visible failure

COMMON MISTAKE

take the largest affordable coin repeatedly

FIX

compute dp[amount] from every reachable dp[amount - coin]

What happens: Greedy is correct for some coin systems but not for arbitrary denominations.
Initialize dp[0] to zero and all other entries to an unreachable marker. For each amount, consider only positive coins not larger than that amount; if dp[amount - coin] is reachable, update dp[amount]. Return None when the target stays unreachable. Reject negative targets and nonpositive denominations before building the table.

Missing the edge condition

COMMON MISTAKE

return infinity for unreachable amount

FIX

return None for unreachable amount

What happens: Target zero requires zero coins.
This algorithm minimizes coin count, not monetary value or weight; denominations define the available moves. Production financial calculations have other constraints and should not infer optimality from a greedy shortcut without proving it for the specific coin system.

Browse this lesson’s problem fixes

VERIFY THE STORY

Sources and further reading

Python list data structures