Rod Cutting asked: what's the maximum profit? Coin Change II asks: how many ways can you reach a target amount? The choice structure is the same. The transition direction is the same. Two things change: max() becomes +, and the initialisation needs one careful adjustment.
If you've been following the series, this chapter should feel like a small variation on something familiar rather than a new problem entirely.
The Problem
Given a list of coin denominations and a target amount, count the number of distinct combinations of coins that sum to that amount. Each coin can be used any number of times.
coins = [1, 2, 5]
amount = 5
Ways to make 5:
5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
Answer = 4
Note that 2 + 2 + 1 and 1 + 2 + 2 count as the same combination. Order doesn't matter here — it's combinations, not permutations.
Where It Sits in the Pattern
The choice diagram is the standard TAKE / SKIP fork. And since the same coin can be used multiple times, it's Unbounded Knapsack. Since you're counting how many ways rather than finding a maximum, the operation is + instead of max().
Here's how the operation changes across the problems you've seen so far:
| Problem | Question | Operation |
|---|---|---|
| 0/1 Knapsack | Maximum value | max() |
| Subset Sum | Possible or not | or |
| Count of Subsets | How many ways (each item once) | + |
| Rod Cutting | Maximum profit | max() |
| Coin Change II | How many ways (unlimited use) | + |
Coin Change II looks like Count of Subsets, but with one critical difference in the TAKE branch.
The Difference From Count of Subsets
Count of Subsets (from Chapter 4) also counted ways using +. But each element could only be used once, so TAKE moved to the previous row.
Coin Change II allows unlimited use, so TAKE stays on the same row.
Count of Subsets (0/1):
T[i][j] = T[i-1][j - arr[i-1]] ← previous row
+ T[i-1][j]
Coin Change II (Unbounded):
T[i][j] = T[i][j - coins[i-1]] ← same row
+ T[i-1][j]
One index. Completely different behaviour.
The DP State
T[i][j] = number of ways to make amount j
using the first i coins
T[3][5] means: using only the first three coin denominations, how many combinations make 5?
Final answer: T[n][amount].
Initialisation
Two boundaries to think through.
No coins available (i = 0): You can't make any positive amount with zero coins. T[0][j] = 0 for all j > 0. This is already handled by initialising the table to zero.
Amount zero (j = 0): There is exactly one way to make amount zero: choose nothing. The empty combination. So T[i][0] = 1 for every i.
for i in range(n + 1):
T[i][0] = 1
This is different from Count of Subsets in Chapter 4, where you initialised only T[0][0] = 1 and let the transition handle zeros in the array. Here there are no zero-valued coins to worry about (coin denominations are always positive), so initialising the entire first column to 1 is safe and correct.
The Transition
When the coin fits (coins[i-1] <= j):
T[i][j] = T[i][j - coins[i-1]] # TAKE: same row
+ T[i-1][j] # SKIP: previous row
We add because we're counting. Ways from TAKE plus ways from SKIP gives total ways.
When the coin doesn't fit (coins[i-1] > j):
T[i][j] = T[i-1][j] # only SKIP
The Complete Code
class Solution:
def change(self, amount, coins):
n = len(coins)
# T[i][j] = number of ways to make amount j
# using the first i coins
T = [[0] * (amount + 1) for _ in range(n + 1)]
# Amount 0 has exactly one combination: choose nothing
for i in range(n + 1):
T[i][0] = 1
for i in range(1, n + 1):
for j in range(1, amount + 1):
if coins[i - 1] <= j:
# TAKE: same row (unbounded — coin can be used again)
# SKIP: previous row
# Add because we are counting ways
T[i][j] = (
T[i][j - coins[i - 1]]
+ T[i - 1][j]
)
else:
# Coin too large — only SKIP
T[i][j] = T[i - 1][j]
return T[n][amount]
A Dry Run
For coins = [1, 2, 5], amount = 5:
After filling the table with coin 1 (row 1), every amount from 1 to 5 has exactly 1 way (all ones). After adding coin 2 (row 2), each amount gains ways that combine 2s with 1s. By the time coin 5 (row 3) is added, T[3][5] captures all four combinations.
The key cell to trace: T[2][4] with coins [1, 2].
coins[1] = 2, j = 4
2 <= 4 → fits
T[2][4] = T[2][4-2] + T[1][4]
= T[2][2] + T[1][4]
T[2][2] is at the same row, meaning: how many ways to make 2 using coins [1, 2]? That's 2 (either 2 or 1+1). T[1][4] is using only coin 1 to make 4: exactly 1 way (1+1+1+1). So T[2][4] = 2 + 1 = 3. Three ways to make 4 using coins [1, 2]: 2+2, 2+1+1, 1+1+1+1.
Three Things to Keep Straight
Why +? You're counting ways. Ways from TAKE plus ways from SKIP.
Why same row on TAKE? Unlimited coin use. Same coin available after picking it.
Why T[i][0] = 1? Amount zero has one valid combination: pick nothing.
Quick Revision
T[i][j] = number of ways to make amount j using first i coins
Initialisation:
T[i][0] = 1 for all i (empty combination makes 0)
T[0][j] = 0 for all j > 0 (no coins, no ways)
Transition:
if coins[i-1] <= j:
T[i][j] = T[i][j-coins[i-1]] + T[i-1][j]
else:
T[i][j] = T[i-1][j]
Key: same row + + = Unbounded counting problem
What You Now Understand
Coin Change II is Count of Subsets made unbounded. The + comes from counting. The same-row TAKE comes from unlimited use. The T[i][0] = 1 initialisation comes from the empty combination being a valid answer for amount zero.
Chapter 10 covers Coin Change I, where the question shifts again: instead of counting how many ways, you want the minimum number of coins. The transition flips from + to min(), and the initialisation needs a different starting value for the same reason Count of Subsets used None instead of False — the default value can't be a valid answer.
Top comments (0)