Chapter 17: A Cousin of Balloons - Minimum Cost to Cut a Stick

The Interval DP pattern we learned in "Burst Balloons" is incredibly powerful, and the best way to master it is to see it in a different context. LeetCode's "Minimum Cost to Cut a Stick" (Problem #1547) is the perfect encore. It feels different on the surface, but the core recursive insight is almost identical.

Instead of bursting the last balloon in an interval, we will be deciding on the first cut to make in a segment. This decision splits the segment into two smaller, independent segments, giving us the clean subproblem structure we need for dynamic programming.

The Problem:

Given a wooden stick of length n units. The stick is labeled from 0 to n. You are given an integer array cuts where cuts[i] denotes a position you should perform a cut.

You should perform the cuts in some order. The cost of one cut is the length of the stick segment you are cutting. When you cut a stick segment, it will be split into two smaller segments. The total cost is the sum of costs of all cuts.

Find the minimum total cost to perform all the cuts.

For example:

• n = 7, cuts = [1, 3, 4, 5]

• Output: 16

• Explanation: If we cut in the order [3, 5, 1, 4]:

  1. Cut at 3 on stick [0, 7]. Cost = 7. Segments are [0, 3] and [3, 7].

  2. Cut at 5 on stick [3, 7]. Cost = 4. Segments are [3, 5] and [5, 7].

  3. Cut at 1 on stick [0, 3]. Cost = 3. Segments are [0, 1] and [1, 3].

  4. Cut at 4 on stick [3, 5]. Cost = 2. Segments are [3, 4] and [4, 5]. Total cost = 7 + 4 + 3 + 2 = 16.

The Key Insight: The First Cut in an Interval

Just like with the balloons, if we ask "what is the next cut to make?", the subproblems get tangled. Instead, we ask "For a given segment of the stick, what is the first cut we should make within that segment?".

Let's say we're considering a stick segment that runs from left_boundary to right_boundary. If we choose to make our first cut at cuts[k], the cost of this single action is right_boundary - left_boundary. After this cut, we are left with two completely independent subproblems:

1. Find the minimum cost to cut the segment from left_boundary to cuts[k].

2. Find the minimum cost to cut the segment from cuts[k] to right_boundary.

This gives us our recurrence. To make it easier to work with, we'll first add 0 and n to our cuts array and sort it. This gives us a complete set of boundaries. solve(i, j) will then find the minimum cost to cut the stick between the i-th and j-th boundary points in our sorted list.

min_cost(i, j) = (cuts[j] - cuts[i]) + min( min_cost(i, k) + min_cost(k, j) ) for all k from i+1 to j-1.

Approach 1: The Recursive Solution

We'll add 0 and n to cuts, sort it, and then define a recursive function solve(i, j) that operates on the indices of this new boundary array.

from typing import List

def minCost_recursive(n: int, cuts: List[int]) -> int:
    # Add the stick boundaries and sort
    cuts = sorted([0] + cuts + [n])

    def solve(i, j):
        # Base case: if there are no cuts to be made between i and j
        if i + 1 >= j:
            return 0

        min_val = float('inf')
        # k is the index of the first cut to be made in the segment (cuts[i], cuts[j])
        for k in range(i + 1, j):
            cost = (cuts[j] - cuts[i]) + solve(i, k) + solve(k, j)
            min_val = min(min_val, cost)

        return min_val

    return solve(0, len(cuts) - 1)

# Trying it out
# print(minCost_recursive(7, [1, 3, 4, 5])) # 16
# This will be very slow due to re-computations.

Approach 2: Memoization with a Decorator (Top-Down DP)

The state (i, j) is cacheable, so we can use our trusty decorator to optimize the recursion.

import functools
from typing import List

class Solution:
    def minCost_memoized(self, n: int, cuts: List[int]) -> int:
        cuts = sorted([0] + cuts + [n])

        @functools.lru_cache(maxsize=None)
        def solve(i, j):
            if i + 1 >= j:
                return 0

            min_val = float('inf')
            # k is the index of the first cut
            for k in range(i + 1, j):
                cost = (cuts[j] - cuts[i]) + solve(i, k) + solve(k, j)
                min_val = min(min_val, cost)

            # If no cuts were found in the loop (e.g. j=i+1), we must return 0
            return min_val if min_val != float('inf') else 0

        return solve(0, len(cuts) - 1)

# Trying it out
# solver = Solution()
# print(solver.minCost_memoized(7, [1, 3, 4, 5])) # 16

The memoized solution has a time complexity of O(m^3), where m is the number of cuts, because there are O(m^2) states (i, j) and each involves an O(m) loop.

Approach 3: Iteration (Bottom-Up DP)

We follow the same iterative structure as "Burst Balloons."

1. Create the sorted boundaries array (cuts + 0 + n).

2. Create a dp table of size m x m.

3. Iterate over interval length l, from 2 up to m.

4. Iterate over the start index i. The end index j will be i + l.

5. Inside, iterate through all possible first cuts k to find the minimum cost for dp[i][j].

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

    # l is the length of the interval of indices in the boundaries array
    for l in range(2, m):
        # i is the start index
        for i in range(m - l):
            j = i + l
            dp[i][j] = float('inf')
            # k is the index of the first cut
            for k in range(i + 1, j):
                cost = (boundaries[j] - boundaries[i]) + dp[i][k] + dp[k][j]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][m - 1]

# Trying it out
# print(minCost_iterative(7, [1, 3, 4, 5])) # 16

Conclusion

"Minimum Cost to Cut a Stick" beautifully demonstrates that a single powerful DP pattern can solve problems that appear very different. By recognizing the need to split an interval into independent subproblems, we could apply the exact same "Interval DP" logic from "Burst Balloons." This chapter solidifies that core concept: when faced with a problem on a range or interval, always ask, "Which action—first, last, or somewhere in between—will cleanly divide my problem?"