Coin Change I: When the Default Value Can Break Everything

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:

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.