Coin Change Problem

Analogy categoryAnalogies

Introduction

The coin change problem has two common variants: (1) given coin denominations and a target amount, find the minimum number of coins needed to make that amount (or determine it's impossible), and (2) count the number of distinct ways to make that amount using unlimited supply of each denomination. Both variants assume an unlimited supply of each coin type. A naive recursive approach explores every combination of coin choices and revisits the same remaining-amount subproblem many times, so both variants exhibit overlapping subproblems, and each is built from optimal solutions to smaller remaining amounts, giving optimal substructure — making DP the natural fit.

🏏

Cricket analogy: Figuring out the minimum number of boundary-scoring shots to reach a target score, where a naive approach recomputes the same 'remaining runs needed' subproblem over and over across different shot orders, is exactly the overlapping-subproblems pattern DP solves.

Approach/Syntax

python

# Variant 1: minimum number of coins to make `amount`
# dp[a] = fewest coins to make amount a; dp[0] = 0
# dp[a] = min(dp[a - c] + 1) for every coin c <= a that yields a valid dp[a - c]

def coin_change_min(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

# Variant 2: number of distinct ways to make `amount` (order doesn't matter)
# dp[a] = number of ways to form amount a using coins processed so far

def coin_change_ways(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1  # exactly one way to make amount 0: use no coins

    for c in coins:                 # iterate coins in the OUTER loop
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

Explanation

In coin_change_min, dp[a] considers every coin c that could be the last coin used to reach amount a; if dp[a-c] is reachable, using one more coin of type c gives a candidate count of dp[a-c] + 1, and we keep the minimum over all coins. In coin_change_ways, the loop order matters: coins must be the OUTER loop and amount the INNER loop so that each coin is 'decided' once per combination, avoiding counting the same set of coins in different orders as distinct ways (e.g., counting {1,2} and {2,1} separately, which would overcount permutations instead of combinations). Swapping the loop order in the ways variant would instead compute the number of ordered sequences (permutations) rather than unordered combinations.

🏏

Cricket analogy: Deciding which boundary type (four or six) was the 'last shot' to reach a target score and taking the minimum over all options mirrors coin_change_min's dp[a-c]+1 logic, while counting distinct over-by-over run sequences requires fixing the shot type as the outer loop to avoid double-counting reordered overs.

Example

code

coins = [1, 3, 4]
amount = 6

min_coins = coin_change_min(coins, amount)
num_ways = coin_change_ways(coins, amount)

print(f"Minimum coins for {amount}: {min_coins}")  # Minimum coins for 6: 2  (3 + 3)
print(f"Number of ways to make {amount}: {num_ways}")  # Number of ways to make 6: 4
# The 4 combinations are: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+1+4

unreachable = coin_change_min([5, 10], 3)
print(f"Minimum coins for 3 using [5,10]: {unreachable}")  # -1 (impossible)

Output/Complexity

With coins=[1,3,4] and amount=6, the output is 'Minimum coins for 6: 2' (using two 3-coins) and 'Number of ways to make 6: 4' (the four combinations listed in the comment). For an unreachable target like amount=3 with coins=[5,10], coin_change_min correctly returns -1. Both variants run in O(n * amount) time and O(amount) space, where n is the number of coin denominations — for each of the 'amount' subproblems, every coin is checked once. This is the same pseudo-polynomial pattern seen in 0/1 knapsack, since the runtime depends on the numeric value of amount, not just the count of coin types.

🏏

Cricket analogy: Reaching a target of 6 runs using boundaries worth 1, 3, and 4 needs a minimum of two shots (two 3s), while counting the four distinct ways to combine those shot values into 6 runs, and an impossible target like 3 runs using only 5s and 10s correctly signals -1, all in time proportional to shots times target.

Key Takeaways

The minimum-coins variant computes dp[a] = min over all valid coins c of dp[a-c] + 1, with dp[0] = 0.
The count-ways variant iterates coins in the outer loop and amount in the inner loop to count combinations, not permutations.
Both variants run in O(n * amount) time and O(amount) space, a pseudo-polynomial complexity.
An unreachable amount is represented with infinity during computation and converted to -1 (or 0 ways) in the final result.
Loop order is a common source of bugs in the count-ways variant — reversing it changes the answer from combinations to permutations.

Practice what you learned

1. In the minimum-coins variant, what does dp[a] represent?

2. Why must the coins loop be outside the amount loop in the count-ways variant?

3. What is the time complexity of the coin change minimum-coins DP algorithm with n coin types and target amount?

4. What does coin_change_min return when the target amount cannot be formed with the given coins?

Was this page helpful?

Longest Common Subsequence

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#CoinChangeProblem#Coin#Change#Problem#Approach#StudyNotes#SkillVeris