Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Tackling the coin change problem with greedy and dynamic programming

Imagine standing at the register at a Melbourne cafe with a $4.50 tab, holding out a $5 note and wondering how many 20-cent coins the cashier should hand back. That tiny decision is exactly the kind of puzzle the coin change problem codifies: given a set of coin denominations and a target amount, what is the smallest number of coins needed to reach that total? In Australia, the coins in circulation are 5c, 10c, 20c, 50c, $1, and $2, which makes the problem feel especially relevant to anyone who has fumbled through a transaction at the local bakery.

The question shows up constantly in technical interviews, competitive programming on platforms like LeetCode, and even in real-world logistics software built in Sydney and Brisbane. Because it sits at the intersection of greedy algorithms, dynamic programming, and graph theory, mastering it unlocks patterns that transfer to scheduling, knapsack variants, and many optimisation tasks that come up in graduate coursework at universities like UNSW and Monash.

Two main strategies dominate: a greedy method that picks the largest coin first, and a dynamic programming approach that builds up answers for every value from zero up to the target. The greedy approach is fast and elegant, yet it only works for certain coin systems. The DP approach is slower but universally correct, and it also extends to related questions such as counting the number of ways to make change, rather than just the minimum count.

In the sections that follow, we walk through the problem statement, examine both algorithms, compare their trade-offs with a concrete example using Australian denominations, and finish with a clean Python implementation and a few habits that will help you recognise which approach to reach for during a coding interview or while building production software.

Understanding the problem statement

The classic coin change problem takes two inputs: a list of positive integers representing coin denominations, and a non-negative integer representing the target amount. The output is the smallest number of coins whose values sum to the target. If the target cannot be reached using the available denominations, the answer is conventionally -1 or infinity.

Consider an Australian example: given coins [5, 10, 20, 50, 100, 200] (cents) and a target of 470, the optimal answer is one $2 coin, one $1 coin, one 50c coin, and one 20c coin, for a total of four coins. A slightly trickier target is 480, which requires two $2 coins, one 50c coin, one 20c coin, and one 10c coin, again five coins, but the exact mix differs from the 470 case.

A common variation asks for the total number of distinct ways to form the amount, regardless of the count. Another variation limits the supply of each coin, turning the puzzle into a bounded knapsack problem. For the rest of this article we focus on the unlimited-supply, minimum-coin variant, since it is the most frequently asked and the cleanest way to build intuition before tackling the harder forms.

The greedy approach explained

The greedy algorithm is the first thing most people try because it mirrors how we reason about change at the supermarket. Starting from the largest denomination, repeatedly take as many coins as possible without exceeding the remaining amount, then move to the next-largest denomination, and continue until the amount reaches zero.

For Australian coins and a target of 470 cents, the steps would be: take two $2 coins (400), leaving 70; take one 50c coin, leaving 20; take one 20c coin, leaving zero. The algorithm returns 4, which happens to be optimal. Running the same trace on 480 cents gives two $2 coins (400), one 50c coin (50), one 20c coin (20), and one 10c coin (10), totalling five coins, again matching the optimum.

The greedy approach runs in O(n) time after sorting the denominations, which makes it essentially free. Its appeal is therefore not just brevity but performance, and many production systems rely on it precisely because the coin systems they deal with are canonical.

When greedy falls short

To see why greedy is not a universal answer, imagine a country with coins [1, 3, 4] and a target of 6. Greedy picks a 4, then a 1, then a 1, producing three coins. The optimal solution is two 3-cent coins. Greedy is off by one.

The failure happens because taking the largest coin first blocks a better combination later. Whenever the coin system is non-canonical, meaning it contains counterexamples like the [1, 3, 4] case, the greedy choice cannot be trusted. Mathematicians have proved that a coin system is canonical if and only if greedy always matches the optimal solution, and the kind of case analysis required to establish that is reminiscent of the reasoning used in the critical path method.

Australian currency has been engineered to be canonical, partly to make everyday transactions faster, but if you are writing software that must work for arbitrary inputs, you cannot assume that property. This is why dynamic programming remains the safe default.

Building a dynamic programming solution

Dynamic programming shines when a problem has overlapping subproblems and optimal substructure, both of which coin change satisfies. The subproblem is "what is the minimum number of coins to make amount k?" and the optimal substructure says that the answer for k depends on the answers for smaller amounts.

Define dp[i] as the minimum number of coins needed to make amount i, with dp[0] equal to 0 and every other entry initialised to infinity. For each amount from 1 up to the target, iterate over the denominations and update dp[i] = min(dp[i], dp[i - coin] + 1) whenever i - coin is non-negative. At the end, dp[target] is the answer, or infinity if unreachable.

The algorithm runs in O(n × m) time, where n is the target amount and m is the number of denominations, and uses O(n) extra space. For a target of 470 with six Australian denominations, that is roughly 2,820 operations, well under a millisecond on any modern machine and trivial compared to the time a Sydney barista spends counting out change during the morning rush.

Greedy versus dynamic programming at a glance

Both algorithms solve the same problem, but they differ in almost every other dimension. Greedy is iterative and makes a single pass through the sorted denominations, while dynamic programming builds a table of sub-answers and reuses them to construct the final result. That structural difference cascades into the runtime, memory, and correctness characteristics summarised below.

Aspect Greedy approach Dynamic programming
Time complexity O(n log n) with sort, then O(n) O(n × m)
Space complexity O(1) extra O(n) extra
Always optimal? Only for canonical systems Yes, for any denominations
Easy to extend? No, logic is rigid Yes, easy to add constraints
Typical use case Real-time POS in Australia Interview problems, general solvers

The table makes the trade-off explicit. If you know the coin system is canonical, greedy is the right tool for production. If you are writing a library that might be reused or tested against edge cases, DP is the safer choice and a great way to demonstrate algorithmic thinking. For most Australian point-of-sale software, greedy is enough, and the Reserve Bank of Australia's choice of denominations reflects that design constraint. For interview preparation and competitive programming, the DP version is the one to memorise, since the judge may throw arbitrary denominations at your solution.

Python implementation walkthrough

A clean Python function for the DP version looks like this:

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0 and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    return dp[amount] if dp[amount] != float('inf') else -1

The greedy counterpart is even shorter:

def coin_change_greedy(coins, amount):
    coins = sorted(coins, reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

If you want to harden the greedy version, you can validate it against the DP result on a range of inputs and raise an error if they ever disagree. This kind of cross-checking is a habit many engineers in Melbourne's fintech scene adopt when porting code such as red-black tree insertion from C into higher-level languages where invariants can drift.

Practical habits for mastering these patterns

Beyond the algorithm itself, a few habits separate candidates who ace coin change questions from those who freeze. The list below captures what has worked for engineers I have coached in Sydney, Melbourne, and Perth, and applies whether you are studying for an interview or shipping production code.