Cheapest Plank Cuts

Medium2-D Dynamic Programming

Problem

A sawmill has a plank of length length marked from 0 to length, and must cut it at every position listed in cuts (distinct integers strictly between 0 and length). Each cut is made on one piece and costs the current length of that piece.

The cuts can be made in any order. Return the minimum total cost.

Example 1

Input:
length = 10, cuts = [2, 5, 7]
Output:
20

Cut at 5 first (cost 10), then at 2 on the 0–5 piece (cost 5) and at 7 on the 5–10 piece (cost 5).

Example 2

Input:
length = 6, cuts = [3]
Output:
6

Constraints

  • 2 ≤ length ≤ 10^6
  • 1 ≤ cuts.length ≤ min(length - 1, 100)
  • 0 < cuts[i] < length, all distinct, in any order

Hint

Show the first hint

Sort the cut positions and add the two ends 0 and length. A piece is always the stretch between two of these points.

Walkthrough

How to approach it

01Clarify before coding

  • Are the cuts given sorted? No, sort them first.
  • Does a cut cost the original length or the current piece? The current piece containing it.
  • Is the length large? Up to 10^6, so the DP must be over cut points, not over positions.

02Brute force

Try every order of the m cuts, simulate the pieces, and keep the cheapest order.

Cost: O(m! · m): with m = 100 cuts, out of the question.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.