1-D DP: Min/Max to Reach a Target

Some problems ask for the best way to build an exact target from pieces you can reuse: the fewest perfect squares that sum to n, the fewest coins for an amount, the best product when you split a number. They look different, but they share one shape: the state is "how much is left", and each step tries every piece. Learn that shape once and you can reuse it across all of them.

The idea#

Define best(rem) as the answer for a remaining target rem. Try every piece p that fits and recurse on rem - p:

best(rem) = 1 + min(best(rem - p) for each piece p), with best(0) = 0.

Why does this work? A count doesn't care about order. Once you know the cheapest way to make rem - p, adding p on top is the cheapest way that ends in p. Taking the min over every last piece covers every possibility. So you don't need an item index, and the state stays 1-D.

How to spot it#

The wording usually gives it away. Look for these signals in the question.

"Fewest", "minimum number", "maximum product" to reach exactly a value.
Pieces can be reused (squares, coins, word lengths, part sizes).
You only need the best value, not the number of distinct ways. Counting ways is the unbounded knapsack note, where order starts to matter.

Template#

Here is the recurrence from above as a memoized recursion. For a max, swap min for max. For a yes/no, swap it for any.

best(rem):
    if rem == 0:
        return 0
    result = inf                   # inf means "not reachable yet"
    for each piece p with p <= rem:
        result = min(result, 1 + best(rem - p))
    return result
memoize best on rem
answer: best(target), mapping inf to the "impossible" value

You can also fill the same recurrence bottom-up in dp[0..target], left to right. The cost is (target) times (number of pieces). There is a third option too: because each level is "one more piece", BFS from the target down to 0 also works. It stops at the first level that reaches 0.

Pitfalls#

Most of these come from how you handle remainders that can't be built.

A guard such as if rem < -1 lets rem = -1 through. Reject every negative remainder, or never generate one (loop only over pieces that fit).
Looping over pieces that fit the original target at every level, instead of pieces that fit rem. It still terminates, but most calls go negative and waste work.
Using 0 as "impossible" in a min-DP. Use inf so it never wins a min.
Trusting greedy "biggest piece first". It fails on general piece sets; DP is the safe default.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Perfect Squares

A state of (largest square allowed, total so far) is correct but 2-D. The answer for a remainder doesn't depend on which squares built the rest, so rem alone is enough. Loop k from 1 to isqrt(rem), not isqrt(n). Bottom-up this is $O(n \sqrt{n})$ ; check 12 → 3 (4 + 4 + 4) and 13 → 2 (4 + 9).

Hint: Coin Change

Same shape with coins instead of squares. Some amounts are unreachable, so return inf for them and map inf to -1 at the end. Greedy is wrong here: with coins [1, 3, 4] and amount 6, greedy gives 4 + 1 + 1 but 3 + 3 uses 2 coins.

Hint: Integer Break

Maximize a product instead of minimizing a count: best(n) = max(max(k, best(k)) * (n - k)) over k. The max(k, best(k)) lets a part stay whole or be split further. In the answers, 3s win: 3s give more per unit than 2s, and a 4 is as good as 2 + 2.

Hint: Word Break

A boolean version. can(i) is true if some dictionary word matches s[i:j] and can(j) is true. The pieces are words and the target is the end of the string.

Hint: Min Cost Climbing Stairs

Let dp[i] be the cheapest cost to stand on step i: it comes from step i - 1 or i - 2, plus that step's cost. The top is one past the last step.

Key takeaways#

The state is the remaining target; each step tries every piece that fits.
Order of pieces doesn't matter for a min/max, so you don't need an item index.
Unreachable states are inf (or False), never 0.
Greedy "biggest piece first" fails on general coin sets; DP is the safe default.

Core idea#

Build an exact target from reusable pieces at the best cost. The state is the amount left, and each step tries every piece that fits: best(rem) = 1 + min(best(rem - p)), with best(0) = 0.

Key points#

A count does not depend on order, so no item index is needed.
Spot it: "fewest", "minimum number" or "maximum product" to reach exactly a value, with reusable pieces.
Counting distinct ways is a different problem. That is unbounded knapsack, where order matters.
Bottom-up fills dp[0..n] left to right. Perfect Squares runs in $O(n \sqrt{n})$ .
Each level is "one more piece", so BFS from n down to 0 also works.
Greedy "largest piece first" fails on general coin sets. Coins [1, 3, 4], amount 6: greedy uses 3 coins, 3 + 3 uses 2.

Variations#

Problem	Change
Coin Change	Unreachable is `inf`, mapped to `-1` at the end
Integer Break	Max product; `max(k, best(k)) * (n - k)`; prefer 3s
Word Break	Boolean: `can(i)` if a word matches `s[i:j]` and `can(j)`

Template#

best(rem):
    if rem == 0: return 0
    result = inf                   # not reachable yet
    for each piece p with p <= rem:
        result = min(result, 1 + best(rem - p))
    return result
memoize best on rem; map inf to "impossible" at the end

Pitfalls#

A guard like rem < -1 lets rem = -1 through. Reject every negative remainder, or never make one.
In Perfect Squares, looping up to isqrt(n) at every level instead of isqrt(rem). Most calls go negative and waste work.
Using 0 as "impossible" in a min-DP. Use inf so it never wins a min.

Say it in an interview#

"The state is the remaining target. Each step tries every piece that fits."
"Greedy fails on general coin sets, so DP is the safe default."