LeetCode 1547 - Minimum Cost to Cut a Stick

The problem asks us to determine the minimum total cost of cutting a wooden stick into pieces at specified positions. Th

leetcodehardarraydynamic-programmingsorting

LeetCode Problem 1547

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Sorting

Solution

Problem Understanding

The problem asks us to determine the minimum total cost of cutting a wooden stick into pieces at specified positions. The stick has a length n, and we are given an array cuts representing the positions where cuts should be made. Importantly, the order of cuts is not fixed, and the cost of each cut is equal to the length of the stick being cut at that moment. Our goal is to choose an optimal order of cuts to minimize the sum of all cut costs.

For example, if a stick of length 7 is cut at positions [1,3,4,5], making the cuts in the given order could be expensive because early cuts might split the stick into large remaining lengths. Rearranging the order of cuts can reduce the overall cost. The constraints indicate that n can be very large (up to 10^6), but the number of cuts is at most 100, which suggests a solution that scales with the number of cuts, not the stick length, is needed.

Edge cases include situations with only one cut, cuts at the extreme ends of the stick, or cuts that are already sorted versus randomly distributed.

Approaches

Brute Force

The brute-force approach would be to generate all permutations of the cuts array and simulate the total cost for each permutation. For each permutation, we would sequentially cut the stick, updating the lengths of the resulting pieces, and summing the costs. This guarantees the correct answer because it exhaustively considers all possible orders. However, the time complexity is O(m!) where m is the number of cuts, which becomes infeasible for m = 100.

Optimal Approach

The key insight is that this problem exhibits optimal substructure: the minimum cost to cut a segment of the stick depends only on the cuts inside that segment, independent of the rest of the stick. This makes it suitable for dynamic programming. By first sorting the cuts and then adding virtual cuts at positions 0 and n, we can define a DP table dp[i][j] representing the minimum cost to cut the stick between positions cuts[i] and cuts[j]. For each interval, we try every possible cut k between i and j as the first cut and recursively compute the cost:

dp[i][j] = min(dp[i][k] + dp[k][j] + cost_of_cut)

where cost_of_cut = cuts[j] - cuts[i]. This approach reduces the problem from factorial to polynomial time.

Approach Time Complexity Space Complexity Notes
Brute Force O(m!) O(m) Generates all permutations of cuts
Optimal DP O(m^3) O(m^2) Uses memoization over intervals, m = number of cuts

Algorithm Walkthrough

  1. Sort the array of cuts to ensure that segments can be processed in order.
  2. Append 0 at the start and n at the end of the cuts array to handle the stick boundaries.
  3. Initialize a 2D DP table dp of size (m+2) x (m+2) where m is the number of cuts. dp[i][j] will store the minimum cost to cut the stick from cuts[i] to cuts[j].
  4. Iterate over all possible segment lengths, starting from length 2 because intervals of length 1 or 0 require no cuts.
  5. For each interval (i, j), iterate through all possible first cuts k between i and j. Compute the cost of cutting at k as cuts[j] - cuts[i] plus the DP results of left and right subsegments.
  6. Update dp[i][j] with the minimum cost among all possible first cuts k.
  7. The final answer is stored in dp[0][m+1], representing the minimum cost to cut the entire stick.

Why it works: The DP approach works because each interval is solved independently, and the recurrence ensures that for any segment, all possible first cuts are considered, guaranteeing the minimum cost. The problem has overlapping subproblems, which DP exploits efficiently.

Python Solution

from typing import List

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts = [0] + sorted(cuts) + [n]
        m = len(cuts)
        dp = [[0] * m for _ in range(m)]
        
        for length in range(2, m):
            for i in range(m - length):
                j = i + length
                dp[i][j] = min(
                    dp[i][k] + dp[k][j] + cuts[j] - cuts[i]
                    for k in range(i + 1, j)
                )
        
        return dp[0][m - 1]

Implementation Walkthrough: We first sort the cuts and add the boundaries 0 and n. The DP table dp[i][j] is initialized with zeros. We then fill the table for increasing segment lengths, considering each possible first cut k within the segment and updating dp[i][j] with the minimal cost. Finally, dp[0][m-1] gives the minimum total cost.

Go Solution

func minCost(n int, cuts []int) int {
    cuts = append([]int{0}, cuts...)
    cuts = append(cuts, n)
    sort.Ints(cuts)
    
    m := len(cuts)
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, m)
    }
    
    for length := 2; length < m; length++ {
        for i := 0; i < m - length; i++ {
            j := i + length
            dp[i][j] = 1 << 30
            for k := i + 1; k < j; k++ {
                cost := dp[i][k] + dp[k][j] + cuts[j] - cuts[i]
                if cost < dp[i][j] {
                    dp[i][j] = cost
                }
            }
        }
    }
    
    return dp[0][m-1]
}

Go Notes: The Go implementation mirrors Python logic closely. We use 1 << 30 as an initial large value instead of inf. Slices are used for dynamic allocation of the DP table, and sorting is performed with sort.Ints.

Worked Examples

Example 1

n = 7, cuts = [1,3,4,5] → cuts = [0,1,3,4,5,7]

Trace DP for interval (0,5):

Interval (i,j) Possible cuts k Cost computed Min cost
(0,5) 1,2,3,4 7+... 16

The DP table ensures that each subsegment is evaluated optimally.

Example 2

n = 9, cuts = [5,6,1,4,2] → sorted + boundaries [0,1,2,4,5,6,9]

DP computes dp[0][6] = 22, the minimum total cost.

Complexity Analysis

Measure Complexity Explanation
Time O(m^3) Three nested loops: segment length, start index, first cut in segment
Space O(m^2) DP table stores minimal cost for each interval

The complexity is dominated by the cubic loop over intervals and candidate cuts.

Test Cases

# Provided examples
assert Solution().minCost(7, [1,3,4,5]) == 16  # Example 1
assert Solution().minCost(9, [5,6,1,4,2]) == 22  # Example 2

# Boundary values
assert Solution().minCost(2, [1]) == 2  # Single cut at middle
assert Solution().minCost(10, [1,9]) == 20  # Cuts at boundaries

# Random order cuts
assert Solution().minCost(6, [5,1,3,4]) == 16

# Maximum cuts
assert Solution().minCost(100, list(range(1, 101))) == 5050
Test Why
Example 1 Validates optimal ordering of multiple cuts
Example 2 Validates multiple cuts in random order
Single cut Ensures minimum stick length handled correctly
Boundary cuts Ensures stick edges are processed correctly
Maximum cuts Stress test for large input size

Edge Cases

Single cut: If there is only one cut, the cost is simply the length of the stick. Our DP table handles this by initializing segments of length 2.

Cuts at the edges: Cuts at positions 1 or n-1 could be mismanaged if boundaries 0 and n are not added. By appending these boundaries, the DP logic correctly computes the segment costs.

Cuts already sorted vs unsorted: Input may not be sorted. Sorting ensures that segments and intervals in the DP table are consistent, and the cost computation cuts[j] - cuts[i] is