❓ The Problem

You’re given an array of coin denominations (e.g. [1, 2, 5])
and a target amount (e.g. 11).
Return the minimum number of coins needed to make up that amount.
If it's not possible, return -1.

---

🎯 What You’re Really Being Asked

Find the shortest path to a number, using only steps defined by the coins.

For example:

coins = [1, 2, 5]
amount = 11

You could make 11 in a ton of ways:

• 1+1+1+...+1 (11 coins)

• 5+5+1 (3 coins)

• 2+2+2+5 (4 coins)

But you want the way that uses the fewest total coins.

---

💣 Why This Problem Is Confusing

Most people throw this at you:

minCoins[i] = Math.min(minCoins[i], 1 + minCoins[i - coin])

And you’re left going:

• Where is this coming from?

• Why is minCoins[i] being compared to itself?

• What the hell is this “bottom-up” thing and why does it work?

This blog answers all of that.

---

✅ Step-by-Step Plan That Actually Makes Sense

---

🧱 Step 1: Define the Meaning of DP

We create:

minCoins[i] = the minimum number of coins needed to make amount i

We’re going to fill this from 0 up to amount.

---

🚨 Base Case:

minCoins[0] = 0

Why?

Because it takes 0 coins to make amount 0.
(You don’t need anything.)

---

🧱 Initial Setup:

We assume all other amounts are impossible by default.
So we set them to “infinity” (amount + 1 is safe):

let minCoins = new Array(amount + 1).fill(amount + 1);
minCoins[0] = 0;

This says:

“I don’t yet know how to make amount 1, 2, ..., amount —
but I’ll try to find better answers as I go.”

---

🧠 Step 2: Core Logic — Build Up the Answer

Now the key idea:

for (let i = 1; i <= amount; i++) {
  for (let coin of coins) {
    if (i - coin >= 0) {
      minCoins[i] = Math.min(minCoins[i], 1 + minCoins[i - coin]);
    }
  }
}

Let's break it line by line:

---

🔁 Outer Loop: for (i = 1 to amount)

“Let me solve for amount = 1, 2, 3, ..., amount one by one.”

We’re building answers from the bottom up.

---

🔁 Inner Loop: for (coin of coins)

“For this current amount, let me try every coin I have.
Each one could be the last coin used to make this amount.”

---

🔥 The Real Brain of the Algorithm:

minCoins[i] = Math.min(minCoins[i], 1 + minCoins[i - coin]);

🚨 Read this in real words:

“If I use coin c now, then I only need to figure out how to build amount - c.
That’s minCoins[i - coin].
So I take that answer, add 1 (for the current coin), and see if it's better than what I had before.”

---

📈 Example: coins = [1, 3, 4], amount = 6

Let’s walk through how we build minCoins[6].

Start with:

minCoins = [0, ∞, ∞, ∞, ∞, ∞, ∞]
             0   1   2   3   4   5   6

i = 1

• Try 1: 1 + minCoins[0] = 1 + 0 = 1 ✅

• Others invalid

minCoins = [0, 1, ∞, ∞, ∞, ∞, ∞]

i = 2

• Try 1: 1 + minCoins[1] = 1 + 1 = 2

minCoins = [0, 1, 2, ∞, ∞, ∞, ∞]

i = 3

• Try 1: 1 + minCoins[2] = 1 + 2 = 3

• Try 3: 1 + minCoins[0] = 1 + 0 = 1 ✅

minCoins = [0, 1, 2, 1, ∞, ∞, ∞]

i = 4

• Try 1: 1 + minCoins[3] = 1 + 1 = 2

• Try 3: 1 + minCoins[1] = 1 + 1 = 2

• Try 4: 1 + minCoins[0] = 1 + 0 = 1 ✅

minCoins = [0, 1, 2, 1, 1, ∞, ∞]

i = 5

• Try 1: 1 + minCoins[4] = 1 + 1 = 2 ✅

• Try 3: 1 + minCoins[2] = 1 + 2 = 3

• Try 4: 1 + minCoins[1] = 1 + 1 = 2

minCoins = [0, 1, 2, 1, 1, 2, ∞]

i = 6

• Try 1: 1 + minCoins[5] = 1 + 2 = 3

• Try 3: 1 + minCoins[3] = 1 + 1 = 2 ✅

• Try 4: 1 + minCoins[2] = 1 + 2 = 3

minCoins = [0, 1, 2, 1, 1, 2, 2]

✅ Final Answer:

minCoins[6] = 2

You can form 6 using: 3 + 3 or 1 + 1 + 4 → both use 2 coins.

---

🔁 Forward vs Reverse Loop

You don’t need reverse loop in this problem.

Why?

Because every time you do:
minCoins[i] = 1 + minCoins[i - coin],
you’re only reading past values (from smaller i’s)

✅ Those values have already been finalized in earlier steps
✅ So forward loop works just fine

---

You’d use reverse loop only when:

• You must not reuse the same item in the same iteration

• Like in 0/1 Knapsack (where each item can be used at most once)

Not here. You can reuse coins as many times as you like.

---

🔚 Return Value

Finally:

return minCoins[amount] !== amount + 1 ? minCoins[amount] : -1;

If it’s still the "infinity" value → No solution found → return -1
Otherwise, return the best answer.

---

🧠 TL;DR Mental Model

• For each amount i

• Try every coin c

• Think:

“If I use c now, how many coins did it take to form i - c?”
Add 1 for the current coin
Keep the best result

That’s it. That’s the chain reaction you wanted to visualize.

---

💬 Final Thoughts

Coin Change is a classic — not because it's hard,
but because it's so easy to explain badly.

If someone had just said:

“Think of coins as steps, and amount as the top of a staircase.
You’re trying to reach the top with as few steps as possible,
trying every footstep that gets you closer,
and always remembering what the best path to each stair looked like.”

You’d have gotten it on Day 1..