Minimum Cost to Cut a Stick: Interval DP on Segment Boundaries

You have a wooden stick of length n and an array cuts where each cuts[i] is a position where you need to make a cut. The cost of a single cut equals the length of the segment you are cutting. You can reorder the cuts however you like. Return the minimum total cost to make all the cuts.

This is 1547. Minimum Cost to Cut a Stick, a hard problem that is one of the cleanest examples of interval DP you will find on LeetCode. The trick is recognizing that the order of cuts matters because each cut splits a segment into two smaller pieces, and the cost of a cut depends on how long the segment is at the time you cut it. Cut a long segment early and you pay more. Cut it after it has already been shortened by other cuts and you pay less.

Why greedy does not work

Your first instinct might be to always make the cut that splits the longest segment, or always cut in the middle. Neither approach works. Consider n = 7, cuts = [1, 3, 4, 5]. Cutting left to right (1, 3, 4, 5) costs 7 + 6 + 4 + 3 = 20. But cutting in the order 3, 5, 1, 4 costs 7 + 4 + 3 + 2 = 16. The optimal order depends on how each cut affects the sizes of future segments, and no simple greedy rule captures this.

The interval DP formulation

The key insight is to think about intervals between consecutive cut points. Sort the cuts array and add the two endpoints, 0 and n, as boundary values. For the example above, cuts = [1,3,4,5] becomes [0, 1, 3, 4, 5, 7].

Define dp[i][j] as the minimum cost to make all the cuts between boundary index i and boundary index j. The "cost of a cut" at any boundary k between i and j is cuts[j] - cuts[i], the full length of the current segment. That cost is fixed regardless of which k you choose, because you are cutting the segment [cuts[i], cuts[j]] and the cut costs its full length.

The recurrence is:

dp[i][j] = min over all k from i+1 to j-1 of:
    dp[i][k] + dp[k][j] + (cuts[j] - cuts[i])

The term cuts[j] - cuts[i] is the cost of making whichever cut splits this segment. After cutting at position cuts[k], you have two independent subproblems: make all cuts in [cuts[i], cuts[k]] (which is dp[i][k]) and make all cuts in [cuts[k], cuts[j]] (which is dp[k][j]).

Base case: when j = i + 1, there are no cuts to make between adjacent boundaries, so dp[i][i+1] = 0.

Fill the table by increasing interval length. The answer is dp[0][m-1] where m is the length of the extended cuts array (original cuts plus the two boundary values).

Python solution

def minCost(n: int, cuts: list[int]) -> int:
    cuts = sorted(cuts)
    cuts = [0] + cuts + [n]
    m = len(cuts)
    dp = [[0] * m for _ in range(m)]

    for length in range(2, m):
        for i in range(0, m - length):
            j = i + length
            dp[i][j] = float('inf')
            for k in range(i + 1, j):
                dp[i][j] = min(
                    dp[i][j],
                    dp[i][k] + dp[k][j] + cuts[j] - cuts[i]
                )

    return dp[0][m - 1]

The outer loop goes over interval lengths from 2 upward (length 2 means one cut inside). For each (i, j) pair, you try every valid cut point k between them and pick the one that minimizes total cost. By the time you compute dp[i][j], all shorter intervals dp[i][k] and dp[k][j] are already filled.

Step-by-step walkthrough

Complexity analysis

Time: O(m^3) where m is the number of cuts plus 2 (the boundary values). There are O(m^2) intervals, and for each interval you try up to O(m) choices of k. Since m <= cuts.length + 2 and cuts.length <= 100, this is at most about 100^3 = 1,000,000 operations. Very fast.

Space: O(m^2) for the DP table.

The building blocks

Interval DP with segment costs. This problem follows the same structural pattern as Burst Balloons and Matrix Chain Multiplication. You have a sequence of elements. You pick a split point k, pay some cost that depends on the full interval, and recurse on the two halves. The only differences across these problems are what the "cost" formula is and whether you are minimizing or maximizing. Once you internalize this template, you can adapt it to any interval DP problem in minutes.

Sort and pad with boundaries. Before running the DP, you sort the cuts and add 0 and n as sentinels. This converts arbitrary cut positions into a clean sequence of boundary indices that the DP can iterate over. You see the same boundary-padding trick in Burst Balloons (padding with 1s) and in many geometry/interval problems. It eliminates edge cases and lets you write a single unified recurrence.

The cost term is independent of k. A subtle but important point: the cuts[j] - cuts[i] cost does not depend on which k you choose. It factors out of the minimization. This is what makes the recurrence clean. In some interval DP problems the cost term depends on k (like Burst Balloons where the cost is nums[i] * nums[k] * nums[j]), which adds complexity. Here the cost is purely a function of the interval endpoints.

Edge cases to watch for

• Single cut: n = 5, cuts = [2]. Extended: [0, 2, 5]. Only one interval of length 2: dp[0][2] = 5 - 0 = 5. Just cut the stick once, cost equals its full length.
• Cuts at the endpoints: The problem guarantees 1 <= cuts[i] <= n-1, so cuts never coincide with 0 or n. No degenerate cases.
• Already sorted cuts: The sort is harmless if cuts are already in order. No special handling needed.
• Two cuts: n = 10, cuts = [3, 7]. Extended: [0, 3, 7, 10]. dp[0][3] = min(dp[0][1]+dp[1][3]+10, dp[0][2]+dp[2][3]+10) = min(0+3+10, 7+0+10) = 13. Cut at position 3 first (cost 10), then cut [3,10] at 7 (cost 7). Wait, that is 17. Let us check: cut at 7 first (cost 10), then cut [0,7] at 3 (cost 7). Total 17. Or cut at 3 first (cost 10), then at 7 (cost 7). Also 17. But dp says 13. Let us recompute: dp[0][2] = cuts[2]-cuts[0] = 7, dp[1][3] = cuts[3]-cuts[1] = 7, dp[0][1] = 0, dp[2][3] = 0, dp[1][2] = 0. dp[0][3]: k=1 gives 0+7+10=17, k=2 gives 7+0+10=17. Both 17. So the answer is 17, not 13. The key is that either order costs the same when there are only two cuts.

From understanding to recall

Reading through this solution and understanding why interval DP works is the first step. The harder part is reproducing it under pressure: remembering to sort the cuts, pad with boundaries, writing the triple loop in the right order, and knowing that the cost term cuts[j] - cuts[i] goes inside the innermost loop.

Spaced repetition closes that gap. You practice writing the DP from scratch at increasing intervals. After a few reps, the setup (sort, pad, triple loop by length) becomes automatic. When you see a problem about cutting or splitting things with a cost proportional to the size of what you are splitting, your hands know the template.

The interval DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding problems randomly.

Related posts

• Burst Balloons - The classic interval DP problem where you maximize coins by choosing the last element to remove in each interval
• Minimum Cost Tree From Leaf Values - Another "minimize cost by choosing the order of operations" problem, solvable with interval DP or a monotonic stack
• Unique Binary Search Trees - Catalan number DP that iterates over all possible root choices for an interval, sharing the same "try every split point" structure