Introduction

The coin-change family of problems is a standard introduction to dynamic programming because the recurrence is simple but the variants behave differently. Two versions appear most often: finding the minimum number of coins needed to reach a target amount, and counting how many different ways the amount can be formed. They use similar state ideas, but the transition logic is not the same.

Two Common Coin-Change Variants

The first variant asks for the fewest coins needed to make a target amount.

The second variant asks how many distinct combinations of coins can make that amount.

For example, with coins [1, 2, 5] and amount 5:

• minimum coins is 1, because coin 5 exists
• number of combinations is 4

Those four combinations are:

• '5'
• '2 + 2 + 1'
• '2 + 1 + 1 + 1'
• '1 + 1 + 1 + 1 + 1'

So before writing code, be very clear which problem you are solving.

Minimum Coin Change

For the minimum-coin version, define dp[a] as the minimum number of coins needed to make amount a.

The recurrence is:

dp[a] = min(dp[a - coin] + 1) over all usable coins

A bottom-up implementation looks like this:

1def min_coins(coins, amount):
2    inf = float("inf")
3    dp = [0] + [inf] * amount
4
5    for a in range(1, amount + 1):
6        for coin in coins:
7            if coin <= a:
8                dp[a] = min(dp[a], dp[a - coin] + 1)
9
10    return -1 if dp[amount] == inf else dp[amount]
11
12
13print(min_coins([1, 2, 5], 11))
14print(min_coins([2], 3))

This runs in O(amount * number_of_coins) time and is the standard dynamic-programming answer.

Why the Minimum-Coin Recurrence Works

If the last coin used is coin, then the rest of the solution must be an optimal way to make amount - coin. Dynamic programming works because the problem has optimal substructure: an optimal whole solution is built from optimal smaller solutions.

That is why greedy logic is not enough for arbitrary coin systems. A greedy choice that looks locally best can fail globally unless the coin system has special structure.

Counting the Number of Combinations

For the counting version, the state still depends on amount, but the transition rule changes. Here dp[a] means the number of ways to form amount a.

1def count_ways(coins, amount):
2    dp = [0] * (amount + 1)
3    dp[0] = 1
4
5    for coin in coins:
6        for a in range(coin, amount + 1):
7            dp[a] += dp[a - coin]
8
9    return dp[amount]
10
11
12print(count_ways([1, 2, 5], 5))

The order of loops matters here. Iterating over coins first ensures combinations are counted without treating different coin orders as separate answers.

Combinations Versus Permutations

This is one of the most important details in coin-change code. If you loop over amounts first and coins second, you often count permutations instead of combinations.

For example, for amount 3 with coins [1, 2]:

• combination view counts 1 + 2 once
• permutation view would count 1 + 2 and 2 + 1 separately

That is why the loop ordering in the counting version is not accidental.

Top-Down Memoization Version

Some people find the recursive version more natural. Memoization gives the same dynamic-programming benefit.

1from functools import lru_cache
2
3
4def min_coins_top_down(coins, amount):
5    @lru_cache(None)
6    def solve(remaining):
7        if remaining == 0:
8            return 0
9        if remaining < 0:
10            return float("inf")
11
12        best = min(solve(remaining - coin) + 1 for coin in coins)
13        return best
14
15    answer = solve(amount)
16    return -1 if answer == float("inf") else answer
17
18
19print(min_coins_top_down((1, 2, 5), 11))

Bottom-up and top-down both work. The best choice often comes down to readability and recursion depth limits.

Common Pitfalls

The biggest mistake is mixing up the two problem variants. Minimizing the number of coins and counting the number of combinations are different recurrences.

Another mistake is using the wrong loop order in the counting version, which accidentally counts permutations instead of combinations.

People also forget unreachable amounts. For minimum-coin change, some targets cannot be formed and should return a sentinel such as -1.

Finally, do not assume greedy selection works for all coin systems. Dynamic programming is needed precisely because local choices are not always globally optimal.

Summary

• Coin change commonly appears in two forms: minimum coins and number of combinations.
• The minimum-coin version uses min transitions over smaller subamounts.
• The counting version uses additive transitions and careful loop ordering.
• Bottom-up and top-down dynamic programming both work well.
• Be explicit about whether the problem counts combinations or permutations.