The split-point idea, on cut positions instead of matrices
Same "try every last cut" recurrence as matrix chains, now costing the length of the piece being cut. About 13 minutes.
Every cut costs the length of the piece
A carpenter has a 7-metre plank and must cut it at the 1, 3, 4 and 5 metre marks. Each cut costs the length of the piece being cut at that moment. Cutting the whole plank costs 7, whichever mark you pick. After that, the pieces are shorter and cheaper to cut. The order matters.
Think of it as matrix grouping again. Add both ends of the plank to the list of marks. For any stretch between two marks, some cut goes first, and it costs the whole stretch's length.
Try each mark as the first cut
For a stretch, try each mark inside it as the first cut. That cut costs the stretch's length, and leaves two smaller stretches that you've already solved. Keep the cheapest total.
A stretch with no marks inside needs no cuts: cost 0. Fill short stretches first, as before. For the 7-metre plank the best order costs 16: cut at 3 first (7), then the left part (3) and the right part (6).
piece = marks[j] - marks[i] # the cut costs this
Neighbouring points have no cut between them: cost 0.
A stretch is 12 metres long. Cutting at one mark first leaves a left part costing 5 and a right part costing 3. What does that order cost for the stretch?
- A20
- B8
- C12
Show the answer
20. 12 for the first cut, plus 5 and 3 for the two parts: 20.
Minimum cost to cut a stick
You get a stick of length n and a list of positions, cuts, where you must cut it (each strictly between 0 and n). You can make the cuts in any order. Cutting a piece of the stick costs exactly that piece's current length. Return the minimum total cost to make every cut.
n = 7, cuts = [1, 3, 4, 5] → 16
1 ≤ n ≤ 1,000 · 0 ≤ cuts.length ≤ 200 · each cut is a distinct position strictly between 0 and n