In minimum-coins change-making, what does dp[a] hold and how do you mark unreachable amounts?
answer
- one cell per amount, not per coin
- what does amount zero cost?
- each cell looks back by one denomination
- unreachable must not look cheap
- sentinel plus one is still unreachable
basics
~10 sdp[a] holds the fewest coins summing exactly to amount a: one plus the smallest dp[a - c] over each denomination c that fits. Amounts no combination reaches carry an infinity sentinel, never 0.
solid answer
~40 sThe table has one cell per amount from 0 up to the target, and `dp[a]` is the fewest tokens that sum to exactly `a`. The base case is `dp[0] = 0` — zero costs nothing — and every other cell starts at a sentinel meaning "unreachable". Then for each amount in increasing order and each denomination `c <= a`, if `dp[a - c]` is not the sentinel, take `dp[a] = min(dp[a], dp[a - c] + 1)`. On a fare machine stocked only with 7- and 10-unit tokens, `dp[14] = 2`, `dp[17] = 2`, `dp[24] = 3`, and `dp[8]` stays at the sentinel because nothing reaches 8. The answer is `dp[target]`, or "cannot pay exactly" if it is still the sentinel. Cost is O(n * target) time and O(target) space.
go deeper
Be ready to state the state and the base case out loud: one cell per amount, amount zero costs zero coins, and every other cell starts unreachable. Many candidates are stopped right there.
Explain how a cell is computed from strictly smaller amounts, and show that you guard the unreachable sentinel before adding one to it rather than letting it turn into a plausible-looking count.
Show the operational side: fill the table once up to the largest amount the machine can be asked for, answer queries by lookup, and decide what the service returns when a target is genuinely unpayable.
Own the contract around the algorithm: whether an unpayable amount is an error, a rounded partial payment, or a stocking change is a product call, and which denominations are stocked is the lever you actually control.
## The problem You are given a set of `n` denominations, each available in unlimited quantity, and a target amount. You want the fewest coins or tokens that sum to **exactly** the target, or a clear answer that no combination does. This is the minimum-coins form of change-making, and it is the same shape as unbounded knapsack with every item's value set to 1 and the objective flipped from maximize to minimize. ## The state: index by amount, not by denomination The single decision every candidate has to make correctly is what a table cell is *about*. It is about an **amount**, not about a coin. `dp[a]` = the minimum number of coins whose values sum to exactly `a`, using any denominations, each as many times as you like. Why this works: any optimal way of paying `a` ends with *some* coin `c`. Remove that coin and what remains is a way of paying `a - c` — and it must itself be optimal, otherwise you could substitute a cheaper way and improve the whole. That is the optimal-substructure argument, and it is what licenses the recurrence. ## Base case and recurrence ``` dp[0] = 0 dp[a] = 1 + min over all c in denominations with c <= a of dp[a - c] (a > 0) ``` `dp[0] = 0` says the empty selection pays zero with zero coins. Note this is 0 here, **not** 1 — the value 1 belongs to the counting variant, where the empty selection is one *way*. Mixing those two base cases up is one of the most common ways this goes wrong on a whiteboard. ## The sentinel, and why it is not zero Some amounts are simply not payable. With denominations {7, 10}, the amounts 1..6, 8, 9, 11, 12, 13, 15, 16, 18, 19, 22, 23 have no exact representation. Those cells need a value that means "impossible", and that value must be **worse than any real answer**, because the min-taking step will otherwise happily pick it up. Initializing them to 0 is the classic bug: `dp[8] = 0` reads as "amount 8 costs nothing", so `dp[15]` becomes `dp[8] + 1 = 1` and the machine confidently claims one token pays 15. Use a large sentinel (conventionally called infinity) and either guard it explicitly — `if dp[a - c] != INF` — or make it large enough that adding 1 cannot overflow into a small number. Guarding is the safer habit, because a sentinel chosen as the maximum representable value silently wraps when you add to it in fixed-width arithmetic. A negative marker like -1 is also a valid convention, but only if you check for it before arithmetic; feeding -1 into `min(..., dp[a - c] + 1)` produces 0 and the same false answer as above. ## Order of computation Amounts ascend from 1 to the target because `dp[a]` depends only on strictly smaller amounts. By the time you compute `dp[a]`, every `dp[a - c]` is final. This is a plain topological order over the dependency graph of amounts; there is no cleverness in it and no need to iterate to a fixed point. ## A worked trace on 7 and 10 A transit kiosk stocks only 7-unit and 10-unit tokens. | amount | 0 | 7 | 10 | 14 | 17 | 20 | 21 | 24 | 27 | |---|---|---|---|---|---|---|---|---|---| | dp | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | Every amount not listed and not a sum of 7s and 10s stays at the sentinel. Reading `dp[24]`: from 24 - 7 = 17 you get 2 + 1 = 3; from 24 - 10 = 14 you also get 2 + 1 = 3; so 3, and indeed 7 + 7 + 10 = 24. ## Recovering the coins The table gives a count, not a selection. Two ways to get the actual tokens: store, next to each cell, the denomination that produced its minimum, or walk backwards at the end — at amount `a`, find any `c` with `dp[a - c] + 1 == dp[a]`, emit `c`, move to `a - c`, and repeat until 0. The walk costs one step per emitted coin. ## Cost Filling the table is O(n * target) time and O(target) space. Both scale with the *numeric value* of the target, which matters once targets get large — but for a kiosk whose largest fare is a few hundred units, the whole table is filled once at startup and every query afterwards is a lookup. ## The counting cousin The same table shape, over the same amounts, answers "how many ways" if you change the base case to `dp[0] = 1` and the aggregator from `min` to a sum. There is no sentinel in that version: unreachable amounts naturally hold 0 ways. That version also becomes sensitive to loop nesting in a way the min version is not — worth knowing that the two variants are not interchangeable even though the table looks identical.
- The machine must also tell the customer which tokens it will hand back. How do you recover them from the table?Either store the denomination that produced each cell's minimum, or walk backwards at the end: at amount a, find a denomination c with dp[a - c] + 1 == dp[a], emit c, move to a - c, and repeat until you hit 0. The walk costs one step per token emitted, so recovery is proportional to the answer's size, not the table's.
- What changes if you want the number of ways to pay rather than the fewest tokens?Same table indexed by amount, but the base cell becomes 1 instead of 0 — the empty selection is one way — and the aggregator becomes a sum instead of a minimum. No sentinel is needed, because an unreachable amount naturally ends at 0 ways. The counting version also becomes sensitive to loop nesting, which the minimizing version is not.
- The kiosk is asked for an amount above the table you filled. What do you do?Fill the table once up to the largest amount the machine can legally be asked for and treat anything beyond as an input-validation failure, not a recomputation trigger. Extending the table on demand is possible — the recurrence only looks backwards, so you can append cells — but an unbounded target driven by user input is an unbounded allocation.
It is like pricing every amount on a shelf from the cheapest up: to price 24 you only have to glance at the already-priced 14 and 17.
saying these in an interview costs you the question
- Says unreachable amounts should stay 0
- Adds one to the sentinel without guarding it
- Indexes the table by coin index instead of by amount
- Sets the zero-amount cell to 1 in the minimizing version
- Rebuilds the whole table for every single query