1547. Minimum Cost to Cut a Stick

1547

HardTwo-Dimensional Dynamic ProgrammingInterval dynamic programmingInterval DP over sorted cut points

Minimum Cost to Cut a Stick

A wooden stick of length n has marked cut positions given in the array cuts. You may perform the cuts in any order; the cost of a single cut equals the current length of the stick being cut. After a cut, the stick splits into two pieces that are cut independently. Return the minimum total cost to perform all the cuts.

Open official problem prompt ↗

In plain English

Order the cuts to minimize total cost, where each cut costs the length of the segment it lands in at the time it is made.

Picture it like this

Chopping a long baguette at marked spots where every chop costs effort proportional to the piece you are holding: you want to make big pieces smaller early in a balanced way so later chops are cheap.

Example

Input: n = 7, cuts = [1, 3, 4, 5]
Output: 16
Why: Ordering cuts as 3,5,1,4 (or any optimal order) yields total cost 16; e.g. first cut costs 7, then the pieces cost less as they shrink.

Constraints

2 <= n <= 10^61 <= cuts.length <= min(n - 1, 100)1 <= cuts[i] <= n - 1All cuts are distinct

Pattern lesson

See the pattern, then code

Interval DP over sorted cut points

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Add the stick's two ends (0 and n) to the cut list and sort. For a segment bounded by points i and j, the first cut you make inside it costs (points[j] - points[i]) regardless of which interior cut k you choose, and it splits the segment into (i..k) and (k..j). Minimize over k.

New words, made simpleKnow these before the algorithm

Cut point: A marked position where the stick may be cut; the two stick ends are added as fixed boundaries.
Segment: A piece of stick bounded by two boundary points, cut independently once separated.
Order independence within a segment: The first cut in a segment always costs the full segment length no matter which interior point it is.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Try every cut order

Factorial in the number of cuts; infeasible even for modest k.

Permute the cuts and simulate cost.

Time O(k!)Space O(k)

Greedy (cut nearest middle first)

Intuitive but provably suboptimal for arbitrary cut positions.

Always split the largest segment near its center.

Time O(k log k)Space O(k)

Best choiceInterval DP on sorted points

Correct and efficient since cuts.length <= 100 keeps m small.

dp over segments bounded by sorted boundary points, minimizing over the first interior cut.

Time O(m^3)Space O(m^2)

The rule we keep true

Invariant

dp[i][j] is the minimum cost to perform every cut strictly between boundary points i and j, given that segment currently spans points[i] to points[j].

Why this is correct

Reasoning

Whatever cut is made first in the segment (i, j) costs its full current length points[j]-points[i], because the segment is intact at that moment; that length is independent of which interior point k is chosen. Choosing k splits the segment into two smaller segments (i..k) and (k..j) that are then cut independently. Minimizing over all first-cut choices k gives the optimum for the segment.

The algorithm in three movesSay these aloud before coding

1Build points = sorted([0] + cuts + [n])

points = [0,1,3,4,5,7]

2Let dp[i][j] be the minimum cost to make all cuts strictly between points i and j

dp[i][i+1] = 0 (no cut between adjacent points)

3Base case: adjacent points (no interior cut) cost 0

dp[0][5] = min_k(dp[0][k]+dp[k][5]) + (7-0)

4dp[i][j] = min over interior k of dp[i][k] + dp[k][j], plus the segment length points[j]-points[i]

5Grow by increasing gap between i and j; return dp[0][m-1]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readn=7, cuts=[1,3,4,5]

2 · AskBoundary points?

3 · Update statepoints = [0,1,3,4,5,7]

4 · Resultm = 6 boundaries

Key takeaway

Stick ends 0 and 7 added to the cut positions, forming the sorted boundary list.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Boundaries and table
Add the stick ends 0 and n, sort all points, and allocate the dp table over boundary indices.
2
Lines 6-8Grow segments
Length is the gap between boundary indices; length 1 has no interior cut and stays 0.
3
Lines 9-10First-cut minimization
Add the constant segment length points[j]-points[i] once, then minimize over the interior cut k splitting into two sub-segments.
4
Lines 11Answer
dp[0][m-1] spans the entire stick from 0 to n.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single cut: cost is exactly n
Cuts already sorted or reverse-sorted: sorting normalizes either way
Large n with few cuts: complexity depends on cuts count m, not n

Common beginner mistakes

Forgetting to add 0 and n as boundary points
Adding the segment length inside the min over k instead of once outside (it is constant for the segment)
Assuming a greedy midpoint split is optimal, which it is not for uneven cut spacing
Indexing so adjacent boundaries are charged a cost; they must be 0

Check your understanding

Why does the first cut in a segment cost the same regardless of which interior point we choose?

Minimum Cost to Cut a Stick

Minimum Cost to Cut a Stick

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming