~20 minutes · Day 63 · unbounded DP · Python
Tonight you meet Coin Change: given coin denominations and a target amount, return the fewest coins needed to make that amount, or -1 if it cannot be made. Interviewers like it because the first greedy idea feels natural, but the correct solution is the cleanest first lesson in “try every choice, then keep the best smaller answer.”
dp[amount] = 1 + the minimum of dp[amount - coin] over every coin; amounts you can never make stay infinite.
That one sentence is the pattern. dp[a] means: the fewest coins needed to make amount a. Each coin is reusable, so for every amount you ask, “what if the last coin I used was this one?” The remaining amount is smaller, so its answer should already be in the table.
Python lists give us a compact table indexed by amount, and the built-in min keeps the best candidate. Dynamic programming means storing overlapping subproblem answers instead of recomputing them (Wikipedia: dynamic programming).
The brute force recursion is: for the current amount, try every coin, recurse on amount - coin, and take the minimum. If there are k coin types and the target is A, this branches over and over, roughly O(kA) in the worst case. It is slow because the same smaller amounts appear again and again.
def dfs(a):
if a == 0: return 0
best = float("inf")
for coin in coins:
if a - coin >= 0:
best = min(best, 1 + dfs(a - coin))
return best
The repeated work is the giveaway. Amount 6 asks about 5, 3, and 2. Those smaller amounts each ask about even smaller amounts. DP turns those repeated calls into table lookups.
Build the table from 0 up to amount. dp[0] = 0 because zero coins make amount zero. Everything else starts as a stand-in for infinity. In the LeetCode problem, impossible amounts must return -1 (problem statement).
def coinChange(coins, amount):
INF = amount + 1 # bigger than any useful answer
dp = [INF] * (amount + 1) # dp[a] = fewest coins for a
dp[0] = 0 # base case: make zero with zero coins
for a in range(1, amount + 1):
for coin in coins: # try each possible last coin
if a - coin >= 0:
dp[a] = min(dp[a], 1 + dp[a - coin])
return -1 if dp[amount] == INF else dp[amount]
The order matters: amounts go upward, so dp[a - coin] is already known when you need it. Coins can be used again because nothing removes a coin from the choices; every amount gets to try every coin.
A post office has stamp values [1, 5, 8]. What is the fewest number of stamps needed to make exactly 13 cents?
Before opening the reveal: what is the state, what is the transition, and what value marks an impossible amount?
Use the same table. dp[x] means the fewest stamps needed for postage x. The transition is dp[x] = 1 + min(dp[x - 1], dp[x - 5], dp[x - 8]) when those previous amounts exist. Impossible amounts stay infinite until a stamp choice reaches them.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every coin recursively) | O(kA) | O(A) |
| DP table (solve each amount once) | O(Ak) | O(A) |
Here A is the target amount and k is the number of coin types. The DP table pays O(A) memory so each amount is solved once, not rediscovered by many recursion branches.
1. What does dp[a] mean in Coin Change?
dp[a] stores the fewest coins needed to make exactly amount a. The final answer lives at dp[amount].2. Which sentence matches the transition?
coin, the remaining subproblem is amount - coin, then you add one coin.3. Spot the bug in this DP version:
dp = [0] * (amount + 1)
for a in range(1, amount + 1):
for coin in coins:
if a - coin >= 0:
dp[a] = min(dp[a], 1 + dp[a - coin])min would keep a fake best answer.4. Which new prompt uses this pattern?
Solve Coin Change on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:
dp[a], the transition, the base case, and where the answer lives.Watch the NeetCode — Coin Change solution video after your attempt, as the compare step. Listen for the moment where the recursion becomes a table over amounts.