Minimum Cost to Cut a Stick

HardDynamic Programminginterval dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You have a wooden stick of length n, with integer positions marked from 0 to n. You are given an array cuts of distinct positions strictly between 0 and n where the stick must be cut. You may perform the cuts in any order. Each cut splits the piece that currently contains that position into two, and it costs exactly the length of that piece at the moment of the cut. Return the minimum total cost needed to make every cut in cuts. Aim for roughly O(m^3) time where m = cuts.length.

Examples

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Cutting in the order 3, 5, 1, 4 costs 7 + 4 + 3 + 2 = 16. Other orders, such as 1, 3, 4, 5 (cost 20), are worse.
Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
The order 4, 6, 5, 2, 1 costs 9 + 5 + 2 + 4 + 2 = 22, and no order is cheaper.

Constraints

  • 2 <= n <= 10^6
  • 1 <= cuts.length <= min(n - 1, 100)
  • 1 <= cuts[i] <= n - 1
  • All values in `cuts` are distinct

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More interval dp problems