Minimum Cost to Cut a Stick
Understanding the Problem
We have a stick of length n and we need to make all the cuts listed in the cuts array. Each cut costs the current length of the sub-stick being cut, so the order in which we make cuts changes the total cost.
Cutting a long stick first is expensive because we pay for the full length, but the resulting pieces are shorter, so later cuts on those pieces are cheaper. Cutting within a small segment first costs less for those cuts but may cost more later when a larger segment still has to be split.
The question is: in what order should we perform the cuts to minimize the total cost? Making one choice (which cut to do first on a segment) splits the problem into two independent subproblems, the left piece and the right piece. That structure points toward interval DP.
Key Constraints:
2 <= n <= 10^6. The stick can be long, butnis a position value, not the size of an array we iterate over, sondoes not determine the algorithm's complexity.1 <= cuts.length <= min(n - 1, 100). At most 100 cuts. With c = cuts.length, this bound makes an O(c^3) algorithm fast enough.- All cuts are distinct, so there are no duplicate cut positions to handle.
Approach 1: Brute Force (Recursion Without Memoization)
Intuition
Solve the problem recursively. Given a stick segment and a set of cuts to make within it, try each possible cut as the first one, pay the cost (the length of the current segment), and recursively solve the two resulting pieces.
Sort the cuts and add the boundaries 0 and n. The problem becomes: given the boundary points, what is the minimum cost to make all cuts that fall between two of them? For a segment defined by boundary indices i and j, try every cut point k between them, paying boundary[j] - boundary[i] for the current cut, then recursively solve the left segment [i, k] and the right segment [k, j].
Algorithm
- Sort the
cutsarray and prepend 0 and append n to create aboundariesarray. - Define a recursive function
solve(i, j)that returns the minimum cost to make all cuts between boundary index i and boundary index j. - Base case: if
j - i <= 1, there are no cuts to make, so return 0. - For each possible cut point k where
i < k < j, compute the cost asboundaries[j] - boundaries[i] + solve(i, k) + solve(k, j). - Return the minimum cost across all choices of k.
- Call
solve(0, len(boundaries) - 1).
Example Walkthrough
Input:
solve(0, 5) covers the whole stick [0, 7], with cut positions 1, 3, 4, 5 inside it. Every choice of first cut pays the full segment cost of 7, then recurses on the two halves.
- First cut at index 1 (position 1): cost
7 + solve(0,1) + solve(1,5). The left is a base case (0). The rightsolve(1,5)covers [1,7] with cuts 3, 4, 5; its cheapest order costs 12. Total = 7 + 0 + 12 = 19. - First cut at index 2 (position 3): cost
7 + solve(0,2) + solve(2,5).solve(0,2)covers [0,3] (one cut), cost 3.solve(2,5)covers [3,7] with cuts 4, 5; cheapest is 6. Total = 7 + 3 + 6 = 16. - First cut at index 3 (position 4): cost
7 + solve(0,3) + solve(3,5).solve(0,3)covers [0,4] with cuts 1, 3, cost 7.solve(3,5)covers [4,7] (one cut), cost 3. Total = 7 + 7 + 3 = 17. - First cut at index 4 (position 5): cost
7 + solve(0,4) + solve(4,5).solve(0,4)covers [0,5] with cuts 1, 3, 4, cost 10. The right is a base case (0). Total = 7 + 10 + 0 = 17.
The minimum across the four choices is 16, taken by cutting at position 3 first. The same subproblems (such as solve(2,5)) are recomputed across these branches, which is what makes the plain recursion slow.
Code
- Time Complexity: O(2^c * c). Without memoization, the recursion tree has exponentially many nodes. The same subproblem (i, j) gets recomputed many times, leading to exponential blowup.
- Space Complexity: O(c). The recursion depth is at most c (number of cuts), and the boundaries array takes O(c) space.
The recursive function solve(i, j) is called with the same arguments many times, yet there are only O(c^2) distinct (i, j) pairs. Caching each result the first time it is computed removes the repeated work.
Approach 2: Top-Down DP (Memoization)
Intuition
The recursive solution has overlapping subproblems. The pair (i, j) fully determines the answer for a segment, and there are only O(c^2) such pairs. Caching results in a memo table removes the recomputation and brings the exponential solution down to polynomial time.
The logic is unchanged: sort the cuts, add boundaries, and for each segment try every possible first cut. The one addition is that before computing a subproblem, we check whether it is already in the cache. If it is, we return the stored value; otherwise we compute it, store it, and return.
The problem has optimal substructure. Once a cut is made at position k inside a segment, the left and right pieces become independent: the optimal strategy for the left piece does not depend on the order of cuts in the right piece, and the reverse holds too. No cut crosses the position k once it has been made, so the two sides never interact again.
The cost of the first cut on a segment is always the length of that segment, no matter which cuts come after it. That lets us separate the cost of the first cut from the cost of everything that follows and add the two. Trying every candidate as the first cut and taking the minimum therefore searches the full space of orderings.
Algorithm
- Sort the
cutsarray and createboundaries = [0] + sorted cuts + [n]. - Create a 2D memo table of size (c+2) x (c+2), initialized to -1.
- Define
solve(i, j): - If
j - i <= 1, return 0 (no cuts needed). - If
memo[i][j] != -1, return cached result. - Compute cost =
boundaries[j] - boundaries[i]. - For each k from i+1 to j-1, compute
solve(i, k) + solve(k, j)and track the minimum. - Store and return
minimum + cost. - Return
solve(0, len(boundaries) - 1).
Example Walkthrough
Code
- Time Complexity: O(c^3). There are O(c^2) unique subproblems (pairs of indices from the boundaries array of size c+2). For each subproblem, we iterate over at most c possible cut points. Total: O(c^2 * c) = O(c^3).
- Space Complexity: O(c^2). The memo table has O(c^2) entries. The recursion stack depth is O(c).
The top-down approach is efficient, but recursion overhead and cache lookups add a constant-factor cost. The same table can be filled iteratively by processing intervals from shortest to longest, which removes that overhead.
Approach 3: Bottom-Up DP (Optimal)
Intuition
Instead of recursing from the full interval down to base cases, we flip the direction. Start by solving all small intervals (length 2 in the boundaries array, meaning exactly one cut), then build up to length 3, length 4, and so on until we solve the full interval.
This is the classic bottom-up interval DP pattern. We define dp[i][j] as the minimum cost to make all cuts between boundary index i and boundary index j. We fill the table by increasing interval length, and for each interval, we try every possible first cut point.
Algorithm
- Sort the
cutsarray and createboundaries = [0] + sorted cuts + [n]. Letm = len(boundaries). - Create a 2D array
dp[m][m]initialized to 0. - For each interval length
lenfrom 2 to m-1: - For each starting index
ifrom 0 to m-1-len: - Set
j = i + len. - Set
dp[i][j] = infinity. - For each cut point
kfrom i+1 to j-1: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]).- Add the segment cost:
dp[i][j] += boundaries[j] - boundaries[i]. - Return
dp[0][m-1].
Example Walkthrough
Code
- Time Complexity: O(c^3). Three nested loops: the outer loop runs O(c) times for interval lengths, the middle loop runs O(c) times for starting positions, and the inner loop runs O(c) times for cut point choices.
- Space Complexity: O(c^2). The 2D DP table of size (c+2) x (c+2) dominates the space usage.