Lesson 4 Coin Change (Minimum Coins)

Problem

Given a set of coin denominations:

coins = {1, 3, 4}

Find the minimum number of coins needed to make a target amount.

Example:

target = 6
 
3 + 3

Answer:

2 coins

---

Recursive Thinking

Define:

minCoins(x)

Meaning:

Minimum number of coins needed to make amount x.

For amount:

x = 6

Possible first choices:

use coin 1
use coin 3
use coin 4

Resulting subproblems:

1 + minCoins(5)
1 + minCoins(3)
1 + minCoins(2)

Therefore:

minCoins(6)
=
1 + min(
        minCoins(5),
        minCoins(3),
        minCoins(2)
      )

---

State Design

State:

minCoins(x)

Meaning:

Minimum coins required to make amount x.

Only one parameter is needed.

Reason:

The set of available coins never changes.

Unlike Knapsack:

dp[item][capacity]

there is no need to remember:

which coins remain available

because every coin may be reused indefinitely.

The future depends only on:

remaining amount

---

Recurrence

For coin set:

{1, 3, 4}

minCoins(x)
=
1 + min(
        minCoins(x-1),
        minCoins(x-3),
        minCoins(x-4)
      )

---

Base Cases

Exact Solution

minCoins(0) = 0

Meaning:

Need amount 0.
Need 0 additional coins.

Invalid State

minCoins(x < 0) = +∞

Meaning:

This path is impossible.

---

Why Not Use -1 Internally?

Example:

coins = {5,7}
target = 1

If:

minCoins(-1) = -1

Then:

1 + minCoins(-1)
=
0

which incorrectly appears better than valid solutions.

For minimum optimization problems:

Impossible = +∞

must be used internally.

Only convert to:

-1

when returning the final answer.

Example:

if (answer >= INF)
    return -1;

---

Manual Table Example

Coin set:

{1,3,4}

Results:

amount:    0  1  2  3  4  5  6
minCoins:  0  1  2  1  1  2  2

Interpretation:

0 -> []
1 -> [1]
2 -> [1,1]
3 -> [3]
4 -> [4]
5 -> [4,1]
6 -> [3,3]

The DP table stores:

minimum number of coins

not:

which coins were used

---

Solution Reconstruction

The DP value:

minCoins(6) = 2

does not directly store:

3 + 3

To recover the actual solution, trace the winning decisions:

6
→ choose 3
→ remaining 3
→ choose 3
→ remaining 0

Result:

3 + 3

This process is called:

Solution Reconstruction

---

Coin Change vs Knapsack

0/1 Knapsack

State:

(item, capacity)

Decision:

take item
skip item

Constraint:

each item can be used at most once

---

Coin Change

State:

amount

Decision:

use coin 1
use coin 3
use coin 4
...

Constraint:

coins remain available after use

A coin can be reused indefinitely.

---

Invalid State Rules

Counting Problems

invalid state = 0

Examples:

Climbing Stairs
Number of Ways

---

Minimum Problems

invalid state = +∞

Examples:

Coin Change
Shortest Path
Minimum Cost

---

Maximum Problems

invalid state = -∞

Examples:

Maximum Profit
Maximum Score

---

Key Lessons

State Principle

A state must contain exactly the information needed to determine the future.

Ask:

If two situations have the same state,
must they have the same answer?

If yes, the state may be sufficient.

---

DP is History Compression

The path used to reach a state is usually irrelevant.

Example:

remaining amount = 6

Once we arrive at 6, the future is identical regardless of how we got there.

DP keeps:

the state

and discards:

the history

---

Recursive Derivation First

A useful workflow:

1. Define recursive state
2. Write recurrence
3. Define base cases
4. Add memoization
5. Convert to bottom-up if needed

This is often easier than designing the DP table directly.