Dissecting the DP Coin Change Problem

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 12noCoins: 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 0for (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

ConceptInsightnoCoins[i]Stores min # of coins to make iInitialize with amount+1Acts like “infinity” so any real count will be smaller13s in the tableMeans that amount can’t be made with given coinsEach amount = graph nodeCoins are edges that move you forward in the graphDP = shortest path finderFinds the fewest coins (like BFS)Track lastUsedCoin[]Allows reconstruction of one valid combinationUse 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.