Skip to main content

1547. Minimum Cost to Cut a Stick

hard

Given a stick and cut positions, find the order that minimizes the total cost where each cut costs the current piece length. Interval DP — the same shape as Burst Balloons and matrix-chain multiplication.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a wooden stick of length n units. The stick is labelled from 0 to n. You are given an integer array cuts where cuts[i] denotes a position you should perform a cut at. You should perform the cuts in order, you can change the order of the cuts as you wish. The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. The cost of cutting a stick will be recorded before the cuts. Return the minimum total cost of the cuts.

Constraints

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

Examples

Example 1

Input
n = 7, cuts = [1,3,4,5]
Output
16

Explanation: Cut order 3,5,1,4 gives total cost 7+4+3+2=16.

Example 2

Input
n = 9, cuts = [5,6,1,4,2]
Output
22

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sort cuts and add sentinels 0 and n. Now consider intervals between consecutive cut indices.

Hint 2

dp[i][j] = min cost to perform all cuts strictly between sorted positions[i] and positions[j]. Empty if j - i <= 1.

Hint 3

Transition: dp[i][j] = min over k in (i, j) of dp[i][k] + dp[k][j] + (positions[j] - positions[i]).

Solution approach

Reveal approach

Interval DP after augmenting the cut list with sentinels. Sort cuts and prepend 0 and append n into positions; let m = positions.length. Define the subproblem dp[i][j] = minimum total cost to perform every cut strictly between positions[i] and positions[j] on the sub-stick of that span. The recurrence relation is dp[i][j] = 0 if j - i <= 1 (no interior cut), else dp[i][j] = min over k in (i, j) of dp[i][k] + dp[k][j] + (positions[j] - positions[i]) — choose which interior cut k is performed first; this cut costs the current sub-stick length (positions[j] - positions[i]) and splits the work into two independent sub-intervals. Fill dp by increasing span (j - i from 2 upward) so subproblems are ready when needed. The answer is dp[0][m - 1]. Time O(m^3), space O(m^2). Because m <= 102 (cuts.length + 2), this comfortably fits the constraints even though n itself is up to 10^6.

Complexity

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

Related patterns

  • dynamic-programming
  • memoization-recursion
  • interval-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Minimum Cost to Cut a Stick and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →