One-dimensional Dynamic Programming
Building up to a target
The state is an amount rather than a position, and every option is available at every step.
Key idea
The state is the remaining target
So far the state has been a position in the input. Here it is a quantity: the answer for amount a is the fewest pieces needed to reach exactly a.
The transition is one term per available piece: using that piece leaves a smaller amount, whose answer is already known. Take the best of those and add one.
Why it works
Represent impossible, do not confuse it with zero
An unreachable amount must be distinguishable from an amount reachable with zero pieces. Using zero for both makes every amount look free.
Infinity works and lets the comparison run without a special case. A sentinel such as target plus one also works and keeps everything as integers. Whichever you pick, convert it to the required failure value at the end and never let it escape.
Tip
Why every piece is available at every amount
The inner loop tries every size at every amount, which is what unlimited reuse means. This is the same distinction as U10's index control, in a different setting: passing the current index there allowed reuse, and looping over all sizes here does the same.
If each piece could be used only once, this loop would be wrong, and the fix is a second dimension in the state. That is the knapsack shape and it appears at the end of this unit.
Gotcha
Fill amounts in increasing order
Each cell reads cells for smaller amounts, so those must already be final. Iterating the amounts downward, or in an arbitrary order, reads values that have not been computed.
The general rule for any table: work out which cells a cell depends on, and choose an order where those are always filled first. Getting this backward is the most common table bug and it produces answers that are too large rather than an error.
Key idea
The counting version is a different loop
Asking how many combinations reach the target, rather than how few pieces, looks like a small change and is not. Counting combinations requires the outer loop to run over the pieces and the inner over the amounts, or the same combination gets counted in several orders.
That distinction is genuinely subtle and it is the subject of a problem in Unit 15. For now, notice that minimizing is order-insensitive and counting is not.
Cost
Cost
The table has one cell per amount and each cell tries every piece, so O(target times pieces) time and O(target) space.
Notice that the target is a value, not an input length. A large target with few pieces is expensive even though the input is tiny, which is worth saying out loud since it looks linear at a glance.
Find the ordering bug
This is meant to find the largest number of pieces that sum to exactly the target, reusing sizes freely. It reports that almost every target is impossible. Click the line that is wrong.
This activity type is not wired up yet.
Coin Change
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.