Minimum Cost to Cut a Stick (LeetCode 1547)

The problem

A wooden stick has length n, with positions 0 to n. You must make every cut listed in cuts, in any order you choose. Each cut costs the length of the piece being cut at that moment. Return the minimum total cost.

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

Cut at 3 first (cost 7). Then cut the left piece [0, 3] at 1 (cost 3), and the right piece [3, 7] at 5 (cost 4) and at 4 (cost 2). Total 7 + 3 + 4 + 2 = 16.

How to think about it

Start with brute force. Try every order of the m cuts: m! orders. With 100 cuts, impossible.

The key insight: the first cut splits the problem into two independent ones. Once you cut a piece at position c, the left and right halves never interact again. So the cost of finishing a piece is: its own length (for whichever cut you make first in it) plus the best cost of each half.

Index by cuts, not by length. n can be a million, so don’t build a table over positions. Sort the cuts and add the ends: cuts = [0, 1, 3, 4, 5, 7]. A piece is now a pair of indices (l, r) into this list, and the cuts strictly between them are the ones it still needs. Then:

dp[l][r] = min over l < k < r of dp[l][k] + dp[k][r] + (cuts[r] − cuts[l])

A piece with no cuts inside (r = l + 1) costs 0.

Which pattern is this? Interval DP, the same shape as Burst Balloons or Matrix Chain Multiplication. The tell is “the order of operations on a range changes the cost”: pick one operation that splits the range, and recurse on both sides.

Approach

1. Sort [0] + cuts + [n] into cuts, with m = len(cuts).
2. Create an m × m table of zeros.
3. For length from 2 to m - 1, and each l, let r = l + length.
4. Set dp[l][r] to the min over every middle k of dp[l][k] + dp[k][r], plus the piece length cuts[r] - cuts[l].
5. Return dp[0][m - 1].

Solution

def minCost(n, cuts):
    cuts = sorted([0] + cuts + [n]); m = len(cuts)       # add the stick's ends
    dp = [[0] * m for _ in range(m)]
    for length in range(2, m):                           # shorter pieces first
        for l in range(m - length):
            r = l + length
            # cut first at k: pay this piece's length, then solve both halves
            dp[l][r] = min(dp[l][k] + dp[k][r] for k in range(l + 1, r)) + cuts[r] - cuts[l]
    return dp[0][m - 1]
# minCost(7, [1,3,4,5]) -> 16

Dry run

cuts = [0, 1, 3, 4, 5, 7]. Each row is a piece by its end positions, the cut chosen first in it, and the cost.

The whole stick: cut at 3 first, dp[0,3] + dp[3,7] + 7 = 3 + 6 + 7 = 16.

Complexity

• Time: O(m³), where m is the number of cuts plus 2. There are O(m²) pieces and each tries O(m) first cuts. It does not depend on n.
• Space: O(m²). For the table.

Edge cases and pitfalls

• One cut costs exactly n.
• Forgetting to sort the cuts breaks the “cuts strictly between l and r” meaning.
• A table over positions 0..n is O(n²) memory, which fails when n is large. Index over cuts instead.
• Greedy “cut nearest the middle first” is not always optimal; you need the DP.
• Missing the piece length. The + cuts[r] - cuts[l] belongs outside the min, once per piece.

Related problems

• Burst Balloons (LeetCode 312): the same interval DP, thinking about the last action instead of the first.
• Stone Game (LeetCode 877): interval DP on a shrinking range.
• Partition Array for Maximum Sum (LeetCode 1043): splitting an array, but with independent blocks so 1-D DP is enough.