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.

1sizes = [1, 2, 5]2 3# Fewest pieces needed for totals 0 through 5, already worked out.4best = [0, 1, 1, 2, 2, 1]5 6amount = 67candidates = [best[amount - size] + 1 for size in sizes if size <= amount]8print("one more piece on top of:", [amount - size for size in sizes])9print("candidates for 6:", candidates, "-> best is", min(candidates))

Every candidate is one already-solved total plus a single piece.

Find the bug· 5 min

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.

Click the line you think is wrong

Problem· 28 min

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.

One-dimensional Dynamic Programming

129 / 170

One-dimensional Dynamic ProgrammingLesson 5 of 11About 45 min