Coin Change Problem: Dynamic Programming Deep Dive with Java

Every payment system, vending machine firmware, and change-dispensing ATM in the world is quietly solving a version of this problem. When a cashier's drawer runs low on quarters, the register software recalculates optimal change combinations on the fly. When a cryptocurrency exchange breaks a large order into smaller fills, it's optimizing a coin-change variant under the hood. This isn't an academic puzzle — it's load-bearing infrastructure.

The naive approach — try every possible combination recursively — collapses catastrophically at scale. With just 10 coin types and a target of 1000, the recursion tree explodes into millions of redundant sub-problems. The same sub-problems get solved over and over, burning CPU time you'll never get back. Dynamic Programming eliminates that waste entirely by guaranteeing each sub-problem is solved exactly once and its result reused. That's the contract DP makes with you.

By the end of this article you'll be able to implement both the minimum-coins variant and the count-of-ways variant from scratch, explain the recurrence relation cold, optimize from O(amount × coins) space down to O(amount), handle every edge case that trips people up in production and in interviews, and articulate the difference between the two DP approaches well enough to teach it to someone else. Let's build this up piece by piece.

What is Coin Change? — Plain English

The Coin Change problem: given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount. Coins can be reused any number of times (unbounded). Greedy doesn't always work — with coins [1, 3, 4] and amount 6, greedy picks 4+1+1=3 coins but the optimal is 3+3=2 coins.

This is the classic unbounded knapsack / complete knapsack problem. Dynamic programming builds the answer bottom-up: first solve for amount 0 (trivial: 0 coins), then for amount 1, 2, ... up to the target, reusing already-computed results.

How Coin Change Works — Step by Step

Define dp[amount] = minimum number of coins to make 'amount'.

1. Initialize dp[0] = 0 (zero coins needed for amount 0).
2. Initialize dp[1..target] = infinity (not yet reachable).
3. For each amount from 1 to target:
4. For each coin denomination c:
5. If c <= amount and dp[amount - c] is not infinity:
6. dp[amount] = min(dp[amount], dp[amount - c] + 1)
7. Return dp[target]. If still infinity, return -1 (impossible).

Time complexity: O(amount * len(coins)). Space: O(amount).

Worked Example — Tracing the Algorithm

Coins = [1, 3, 4]. Target = 6.

Initialize: dp = [0, INF, INF, INF, INF, INF, INF]

amount=1: try coin 1: dp[0]+1=1. dp[1]=1. dp = [0, 1, INF, INF, INF, INF, INF]

amount=2: try coin 1: dp[1]+1=2. dp[2]=2. dp = [0, 1, 2, INF, INF, INF, INF]

amount=3: try coin 1: dp[2]+1=3. try coin 3: dp[0]+1=1. min(3,1)=1. dp[3]=1. dp = [0, 1, 2, 1, INF, INF, INF]

amount=4: try coin 1: dp[3]+1=2. try coin 3: dp[1]+1=2. try coin 4: dp[0]+1=1. min=1. dp[4]=1. dp = [0, 1, 2, 1, 1, INF, INF]

amount=5: try coin 1: dp[4]+1=2. try coin 3: dp[2]+1=3. try coin 4: dp[1]+1=2. min=2. dp[5]=2. dp = [0, 1, 2, 1, 1, 2, INF]

amount=6: try coin 1: dp[5]+1=3. try coin 3: dp[3]+1=2. try coin 4: dp[2]+1=3. min=2. dp[6]=2. dp = [0, 1, 2, 1, 1, 2, 2]

Answer: dp[6] = 2 coins. The combination is coin 3 + coin 3.

Implementation

The following implementation demonstrates Coin Change with clear comments.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] != float('inf'):
                dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 3, 4], 6))   # 2  (3+3)
print(coin_change([2], 3))          # -1 (impossible)
print(coin_change([1, 5, 6, 9], 11))# 2  (5+6)

Frequently Asked Questions