Hey fellow coders,

Let’s talk about one of those classic dynamic programming problems that haunts us all at some point: Coin Change.

You know the one:

“Given an array of coins and a target amount, return the minimum number of coins that make up that amount.”

Sounds simple enough, right? But if you’ve ever stared at noCoins[i] = min(noCoins[i], noCoins[i - coin] + 1) and wondered what is even going on here, you are not alone.

In this post, I’ll walk you through how I went from confused to clicking when it comes to:

• What the DP array means
• Why we fill it with amount + 1
• Why values like 13 show up
• How this is just a graph in disguise
• And how to actually recover all combinations, not just the count

Let’s get into it!

The Setup

You’re given:

coins = [2, 5, 10]
amount = 12

You want to know:
What’s the minimum number of coins you can use to sum up to 12?

Dynamic programming is the way to go, and that means we’ll use an array like this:

int[] noCoins = new int[amount + 1];

Where:

• noCoins[i] = the minimum number of coins to make amount i

Step 1: Initialize with “Infinity”

We fill the array like this:

Arrays.fill(noCoins, amount + 1);
noCoins[0] = 0;

Why amount + 1 (a.k.a. 13 in our example)?
Because:

• It’s guaranteed to be more than the worst-case number of coins needed
• It acts like a stand-in for “not possible” or “infinity”
• We’ll overwrite it later with real values if a solution exists

So initially, for amount = 12, our table looks like:

noCoins = [0, 13, 13, 13, ..., 13]

---

Step 2: Build Up Solutions from Small to Big

Here’s the key insight:
You don’t solve 12 directly.
You build up from 1 to 12, asking at each step:

“What’s the best way to make this amount using the coins I have?”

You loop through every amount from 1 to 12, and for each one, you try every coin:

for (int curAmount = 1; curAmount <= amount; curAmount++) {
    for (int coin : coins) {
        if (coin <= curAmount) {
            noCoins[curAmount] = Math.min(noCoins[curAmount], noCoins[curAmount - coin] + 1);
        }
    }
}

If you’re at curAmount = 7 and trying coin 2, you say:

• “If I already know how to make 7 - 2 = 5, and that takes 1 coin, then I can make 7 by adding 1 more coin.”
• So noCoins[7] = min(noCoins[7], noCoins[5] + 1)

This simple idea builds the entire table from the ground up.

Example: coins = [2, 5, 10], amount = 12

You’ll end up with:

makefileCopyEditAmount:
0   1   2   3   4   5   6   7   8   9  10  11  12
noCoins:    
0  13   1  13   2   1   3   2   4   3   1   4   2

Let’s decode this:

• noCoins[2] = 1 → use one 2
• noCoins[5] = 1 → use one 5
• noCoins[12] = 2 → you can make $12 using just two coins: maybe [2, 10] or [5, 5, 2]

But what about those scary 13s?

• noCoins[1] = 13 → you can’t make $1 using only coins {2, 5, 10}
• noCoins[3] = 13 → same deal for $3

The 13s just mean “unreachable with current coins.”

---

Why This Is Just a Graph

You can think of each amount as a node in a graph, and each coin is an edge that jumps you forward:

0 --(+2)--> 2 --(+2)--> 4 ...
 \--(+5)--> 5 --(+2)--> 7 ...
 \--(+10)-> 10 ...

You’re essentially exploring all possible paths to get to node 12.

• The DP approach stores the shortest path (fewest coins) to each node
• Just like BFS in a graph, we go layer by layer

Want to Know What Coins Were Used?

Just track which coin was last used to reach each amount:

int[] lastUsedCoin = new int[amount + 1];

if (noCoins[curAmount - coin] + 1 < noCoins[curAmount]) {
    noCoins[curAmount] = noCoins[curAmount - coin] + 1;
    lastUsedCoin[curAmount] = coin;
}

Now you can retrace your steps from amount back to 0:

int curr = amount;
List<Integer> combo = new ArrayList<>();
while (curr > 0) {
    combo.add(lastUsedCoin[curr]);
    curr -= lastUsedCoin[curr];
}

Boom, you’ve recovered one possible coin combination.

But What If You Want All Possible Combinations?

This is where things get fun. You can build a list of all ways to make each amount by doing this:

List<List<List<Integer>>> combinations = new ArrayList<>();
for (int i = 0; i <= amount; i++) combinations.add(new ArrayList<>());
combinations.get(0).add(new ArrayList<>()); // base: one way to make 0

for (int curAmount = 1; curAmount <= amount; curAmount++) {
    for (int coin : coins) {
        if (coin <= curAmount) {
            for (List<Integer> prev : combinations.get(curAmount - coin)) {
                List<Integer> newCombo = new ArrayList<>(prev);
                newCombo.add(coin);
                combinations.get(curAmount).add(newCombo);
            }
        }
    }
}

Now combinations.get(12) holds every way you can make 12 with your coin set!

Wrapping It All Up

Concept	Insight
noCoins[i]	Stores min # of coins to make i
Initialize with amount+1	Acts like “infinity” so any real count will be smaller
13s in the table	Means that amount can’t be made with given coins
Each amount = graph node	Coins are edges that move you forward in the graph
DP = shortest path finder	Finds the fewest coins (like BFS)
Track lastUsedCoin[]	Allows reconstruction of one valid combination
Use List<List<List<Integer>>>	Stores all combinations for each amount

Understanding the coin change problem is like learning a new lens to see DP, graphs, and even recursion in disguise. We’re just walking a graph of totals, building paths one coin at a time.