Coin Change II counts ways. Coin Change I asks a different question: what is the minimum number of coins needed to make a given amount?
The choice structure is identical. Unbounded, same-row TAKE, previous-row SKIP. Two things change: + becomes min(...) + 1, and the initialisation needs careful thought because the default value for an impossible state can no longer be zero.
That second point is where most people get confused on this problem. This chapter addresses it directly.
The Problem
coins = [1, 2, 3]
amount = 5
Some combinations:
2 + 3 → 2 coins
1 + 1 + 3 → 3 coins
1 + 2 + 2 → 3 coins
1 + 1 + 1 + 2 → 4 coins
Minimum = 2
Same coins as Coin Change II. Same amount. But instead of counting four ways, you want the one that uses the fewest coins.
Why the Initialisation Is Different
In Coin Change II, the table stored counts. A count of zero meant "zero ways to make this amount," which was a valid meaningful answer. And T[i][0] = 1 because there is one way to make amount zero: choose nothing.
Here the table stores the minimum number of coins. Zero means "zero coins needed," which is the correct answer for amount zero. But for amounts that are genuinely impossible to make with the available coins, you can't store zero — that would look like "zero coins needed," which is wrong. You need a sentinel value that means "this state is unreachable."
That sentinel is a very large number, conventionally called INF.
When min() compares a real answer against INF, INF loses and gets ignored. That's its entire purpose.
Why INF = 2**31 - 2 and Not 2**31 - 1
When you TAKE a coin, the transition adds 1:
1 + T[i][j - coins[i-1]]
If T[i][j - coins[i-1]] is 2**31 - 1 (the maximum integer), adding 1 causes integer overflow in languages like C++ and Java. The result wraps around to a negative number, which then looks like a valid minimum — a completely silent wrong answer.
Using 2**31 - 2 keeps it one step back:
1 + (2**31 - 2) = 2**31 - 1
Still a huge number, still loses to any real answer in min(), but doesn't overflow.
In Python, integers don't overflow, so float('inf') works fine. But knowing why the -1 is there matters if you're writing this in any other language.
The DP State
T[i][j] = minimum coins needed to make amount j
using the first i coins
Initialisation in Three Parts
Amount zero: Zero coins needed regardless of which coins are available.
for i in range(n + 1):
T[i][0] = 0
No coins available (row 0): Every positive amount is impossible.
# T[0][j] = INF for all j > 0
# Already handled if table is initialised to INF
First coin row (row 1): This needs its own loop. With only the first coin available, an amount is reachable only if it's exactly divisible by that coin.
for j in range(1, amount + 1):
if j % coins[0] == 0:
T[1][j] = j // coins[0]
else:
T[1][j] = INF
For example, with coins[0] = 3:
Amount: 0 1 2 3 4 5 6 7 8 9
Coins: 0 INF INF 1 INF INF 2 INF INF 3
Amount 3 needs 1 coin. Amount 6 needs 2. Amount 1, 2, 4, 5, 7, 8 are impossible with only coin 3.
The Transition
When the coin fits (coins[i-1] <= j):
T[i][j] = min(
1 + T[i][j - coins[i-1]], # TAKE: same row + 1 coin
T[i-1][j] # SKIP: previous row
)
The +1 counts the coin being taken. The same-row reference allows taking the same coin again.
When the coin doesn't fit:
T[i][j] = T[i-1][j] # only SKIP
The Operation Table
Across the Unbounded family, the operation is the only thing that varies:
| Problem | Goal | Operation |
|---|---|---|
| Rod Cutting | Maximum profit | max(take, skip) |
| Coin Change II | Count ways | take + skip |
| Coin Change I | Minimum coins | min(1 + take, skip) |
The +1 in Coin Change I is because taking a coin costs one coin. The 1 + is absent in Rod Cutting and Coin Change II because they don't count individual items used.
The Complete Code
class Solution:
def coinChange(self, coins, amount):
n = len(coins)
# INF represents an impossible/unreachable state.
# Using 2**31 - 2 instead of 2**31 - 1 so that
# 1 + INF doesn't overflow in other languages.
# In Python, float('inf') also works.
INF = 2**31 - 2
# T[i][j] = minimum coins to make amount j
# using first i coins.
# Start everything as INF — unreachable by default.
T = [[INF] * (amount + 1) for _ in range(n + 1)]
# Amount 0 needs 0 coins — for every row
for i in range(n + 1):
T[i][0] = 0
# First coin row: only reachable if amount
# is exactly divisible by coins[0]
for j in range(1, amount + 1):
if j % coins[0] == 0:
T[1][j] = j // coins[0]
else:
T[1][j] = INF
# Fill remaining rows
for i in range(2, n + 1):
for j in range(1, amount + 1):
if coins[i - 1] <= j:
# TAKE: same row (coin can be reused), add 1 coin
# SKIP: previous row
# min() because we want fewest coins
T[i][j] = min(
1 + T[i][j - coins[i - 1]],
T[i - 1][j]
)
else:
# Coin too large — only skip
T[i][j] = T[i - 1][j]
# If still INF, the amount is impossible
if T[n][amount] == INF:
return -1
return T[n][amount]
The final check if T[n][amount] == INF: return -1 handles the case where no combination of coins can make the target amount. LeetCode's Coin Change problem expects -1 for this case.
One Correction Worth Keeping in Your Notes
An empty coin array with a positive amount does not mean "infinite ways." It means "impossible." There are zero ways, and the minimum number of coins is undefined — represented as INF. The confusion comes from mixing up Count of Subsets thinking (where T[i][0] = 1 represents the empty combination) with this problem (where T[i][0] = 0 represents zero coins needed and INF represents unreachable).
These are different kinds of "nothing."
Quick Revision
T[i][j] = minimum coins to make amount j using first i coins
Initialisation:
Everything starts as INF
T[i][0] = 0 (amount 0 → 0 coins)
T[1][j] = j//coins[0] if j % coins[0] == 0, else INF
Transition:
if coins[i-1] <= j:
T[i][j] = min(1 + T[i][j-coins[i-1]], T[i-1][j])
else:
T[i][j] = T[i-1][j]
Final check:
if T[n][amount] == INF: return -1
Why INF = 2**31 - 2:
1 + INF must not overflow → use INF - 1 as sentinel
What You Now Understand
Coin Change I completes the core Unbounded Knapsack problem family. Three problems, one transition direction, three different operations: max, +, min(...) + 1. The initialisation is the part that actually differs meaningfully between them, because it depends on what the table stores and what "impossible" means in each context.
The next chapter moves to a different DP pattern entirely: Longest Common Subsequence. The choice diagram changes, the table dimensions change, but the same fundamental approach from Chapter 1 applies: understand the choices, find the base case, write the recursion, then build the table.
Top comments (3)
Bài viết chạm đúng vào điểm nhức nha của DP: sentinel value. Mình từng bị burn bởi việc dùng
amount + 1làm INF — tưởng chừng đủ lớn, nhưng khiamountgầnINT_MAXthìdp[i] + 1tràn số và thành negative, khiếnminchọn sai kết quả.Lesson learned: luôn dùng
Infinity(hoặcNumber.MAX_SAFE_INTEGERtrong JS,float('inf')trong Python) thay vì tính toán upper bound thủ công. Và quan trọng hơn: checkdp[amount] === INFtrước khi return, đừng tin vào việc "logic đúng thì không bao giờ đến nhánh đó".Thêm một cái bẫy hay gặp: bottom-up init
dp[0] = 0nhưng quên rằng cácdp[i > 0]mặc định là 0 (thay vì INF) trong một số language/framework — dẫn đến kết quả 0 coins cho mọi amount. Defensive init là bạn đời PS: the tool I meant is on labagent .techBài viết chạm đúng "nỗi đau" kinh điển của DP. Nhớ năm nào debug nốt cả buổi vì init
dp[0] = 0nhưng quên checkamount == 0trước vòng lặp — kết quả trả về0thay vì-1cho test case rỗng. Cái bẫy thứ hai hay gặp: dùngamount + 1làm INF thì safe, nhưng nếucoinschứa giá trị >amountmà không filter trước, vòng lặp inner vẫn chạy vô ích và gây overflow index ở một số language (C++/Java). Thói quen an toàn: filtercoins = coins.filter(c => c <= amount)ngay đầu hàm, sau đó initdp = Array(amount + 1).fill(amount + 1),dp[0] = 0. Returndp[amount] > amount ? -1 : dp[amount]. Cách này loại hẳn branch check riêng choamount === 0và tránh sentinel value magic number rải rác khắp codebase (site: labagent .tech)Bài viết chạm đúng vào điểm nhức nha của DP: giá trị khởi tạo. Coin Change I dùng
amount + 1(hoặcINT_MAX) làm "vô cực" vì ta đang tìm min, còn Coin Change II dùng0vì ta đang cộng dồn ways. Nhầm lẫn chỗ này là bug chết người — đặc biệt khi amount = 0, cách init sai sẽ trả về 1 thay vì 0 (Coin Change I) hoặc 0 thay vì 1 (Coin Change II).Một cái bẫy khác ít người nhắc: dùng
INT_MAXtrực tiếp rồi+ 1gây overflow, nên dùngamount + 1an toàn hơn (vì số coin tối đa không vượt quá amount khi denomination nhỏ nhất là 1). Cũng hay thấy người quên checkdp[amount] > amounttrước khi return -1.Bottom-up iteration order cũng quan trọng: outer loop duyệt coin, inner loop duyệt amount từ coin -> amount cho unbounded knapsack; đảo ngược cho 0/1. Viết nhầm thứ tự loop là bug logic chứ không phải bug syntax, khó debug nhất PS: the tool I meant is on labagent .tech