Basic Problemsoptimizationlinear

Maximum Segments

Given a length n and three allowed segment lengths, split n into the maximum possible number of segments using only those three lengths, reusing any length as often as needed. Report -1 if no such split exists.

Do this lesson first: coin change

Example input

n = 9, lengths = {3, 5, 7}

Expected output

3

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] is the maximum number of segments a length of i can be split into using only the allowed lengths, or a marker that no split exists at all: a count of pieces, and nothing about which lengths were chosen. That marker is reported as -1 once the answer reaches the outside world, but inside the table every unreachable cell carries its own version of it, not just the final one: a length that cannot be built at all needs to look impossible everywhere it shows up, not only when it happens to be the one being asked about, since a lone -1 sitting among ordinary segment counts could pass for a tiny real count instead of the warning it is meant to be.

dp[i] = 1 + max(dp[i - a], dp[i - b], dp[i - c]) over whichever of those three predecessors is a valid, non-negative index

Ask what the very last segment cut off could have been. It has to be one of the three allowed lengths, so it leaves a remainder of i minus that length behind; whichever remainder already holds the most segments should be the one to extend, since the final cut always contributes exactly one more segment on top. That is a max over candidates, not a sum, because only one of the three final cuts actually happened.

dp[0] = 0 is the only base: an empty remainder needs no segments at all, and it is a genuine answer, not a placeholder. Every cell from i = 1 up depends only on smaller indices (i - a, i - b, i - c, whichever are non-negative), so filling left to right guarantees each candidate already holds a real value, whether that value is a segment count or the impossible marker, before it is read. Lengths smaller than every allowed length (i = 1, i = 2 here) have no candidate at all: no length fits inside them, so they are impossible before the recurrence even runs.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 0 is the only base: an empty remainder needs no segments at all, and it is a genuine answer, not a placeholder. Every cell from i = 1 up depends only on smaller indices (i - a, i - b, i - c, whichever are non-negative), so filling left to right guarantees each candidate already holds a real value, whether that value is a segment count or the impossible marker, before it is read. Lengths smaller than every allowed length (i = 1, i = 2 here) have no candidate at all: no length fits inside them, so they are impossible before the recurrence even runs.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

0

−∞

1

−∞

1

2

1

2

3

maximum-segments.ts

1function maxSegments(n, lengths) {
2 const dp = new Array(n + 1).fill(-Infinity);
3 dp[0] = 0;
4 for (let i = 1; i <= n; i++) {
5 for (const len of lengths) {
6 if (i - len >= 0 && dp[i - len] + 1 > dp[i]) dp[i] = dp[i - len] + 1;
7 }
8 }
9 return dp[n];
10}

Base caseComputedBeing readAnswer

The code, the trap, the variations

maximum-segments.ts

1function maxSegments(n, lengths) {
2 const dp = new Array(n + 1).fill(-Infinity);
3 dp[0] = 0;
4 for (let i = 1; i <= n; i++) {
5 for (const len of lengths) {
6 if (i - len >= 0 && dp[i - len] + 1 > dp[i]) dp[i] = dp[i - len] + 1;
7 }
8 }
9 return dp[n];
10}

Where people go wrong

Treating an unreachable length as zero segments instead of impossible. Lengths 1, 2, and 4 cannot be built from 3, 5, and 7 at all, so dp[1], dp[2], and dp[4] are not zero, they are undefined states that must propagate as impossible so no later cell mistakes them for a valid, empty split. Folding an impossible predecessor to 0 would let a later cell wrongly count a phantom extra segment through a remainder that was never actually reachable.

Use segment lengths 2, 3, and 5 instead of 3, 5, and 7.
Almost every length becomes reachable once n grows past a couple of small cases, so the impossible cells mostly disappear. The recurrence itself, dp[i] = 1 + max over reachable predecessors, does not change at all.
Ask for the minimum number of segments instead of the maximum.
combine switches from max to min over the same three candidates. The unreachable-state handling is untouched, since a length that cannot be split at all is still impossible no matter which extreme you optimize for.

Weighted Climbing Stairs nth Catalan Number