Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Minimum Cost to Cut a Stick

HARDProblemSolveExternal Links

Description

You have a wooden stick of length n units, labeled from 0 to n. You are given an integer array cuts where cuts[i] represents a position on the stick where you must make a cut.

You may perform the cuts in any order you choose. The cost of making a single cut is equal to the length of the stick segment you are currently cutting. After each cut, the stick splits into two smaller pieces (the sum of their lengths equals the original segment's length).

Return the minimum total cost to make all the required cuts.

The key insight is that the order in which you make the cuts dramatically affects the total cost. Cutting a long stick early is expensive because you pay the full length. If you can arrange to make cuts on shorter segments first, you pay less overall.

Examples

Example 1

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

Output: 16

Explanation:
If we follow the input order [1, 3, 4, 5], the costs are:

  • Cut at 1 on stick [0,7]: cost = 7
  • Cut at 3 on stick [1,7]: cost = 6
  • Cut at 4 on stick [3,7]: cost = 4
  • Cut at 5 on stick [4,7]: cost = 3
  • Total = 7 + 6 + 4 + 3 = 20

But if we reorder to [3, 5, 1, 4]:

  • Cut at 3 on stick [0,7]: cost = 7
  • Cut at 5 on stick [3,7]: cost = 4
  • Cut at 1 on stick [0,3]: cost = 3
  • Cut at 4 on stick [3,5]: cost = 2
  • Total = 7 + 4 + 3 + 2 = 16 ← minimum

Example 2

Input: n = 9, cuts = [5, 6, 1, 4, 2]

Output: 22

Explanation:
Using the given order would cost 25. But the optimal order [4, 6, 5, 2, 1] yields:

  • Cut at 4 on [0,9]: cost = 9
  • Cut at 6 on [4,9]: cost = 5
  • Cut at 5 on [4,6]: cost = 2
  • Cut at 2 on [0,4]: cost = 4
  • Cut at 1 on [0,2]: cost = 2
  • Total = 9 + 5 + 2 + 4 + 2 = 22 ← minimum

Constraints

  • 2 ≤ n ≤ 10^6
  • 1 ≤ cuts.length ≤ min(n - 1, 100)
  • 1 ≤ cuts[i] ≤ n - 1
  • All the integers in cuts array are distinct.

Editorial

Brute Force

Intuition

Imagine you have a wooden plank with several marks where you need to saw it. Each saw costs you effort proportional to the plank's current length. Naturally you wonder: "In what order should I saw to minimize my total effort?"

The most straightforward idea: for any segment of the stick that still has cut points remaining, try every possible cut point as the first cut. Making a cut at position k in a segment [i, j] costs j - i (the segment's length), and splits the problem into two independent sub-problems: the left piece [i, k] and the right piece [k, j], each with their own remaining cuts.

To set this up cleanly, we first add 0 and n as boundary markers to the cuts array and sort it. Now our problem becomes: given the sorted positions [0, 1, 3, 4, 5, 7], find the minimum cost to make all interior cuts.

Without any caching, this recursion revisits the same sub-segments many times. For example, the segment [3, 5] might be encountered when we first cut at 1 then at 3, or when we first cut at 5 then at 3 — same sub-problem, recomputed from scratch each time.

Step-by-Step Explanation

Let's trace with n = 7, cuts = [1, 3, 4, 5]. After adding boundaries and sorting: cuts = [0, 1, 3, 4, 5, 7].

We need solve(0, 5) — minimum cost to handle all cuts between indices 0 and 5 in the sorted array (positions 0 to 7).

Step 1: solve(0, 5) — segment [0, 7], length = 7. We can cut at indices 1, 2, 3, or 4 (positions 1, 3, 4, 5). Try each:

Step 2: Try k=1 (cut at position 1): cost = 7 + solve(0,1) + solve(1,5). solve(0,1) = 0 (no interior cuts). Need solve(1,5).

Step 3: solve(1, 5) — segment [1, 7], length = 6. Try k=2,3,4.

Step 4: Try k=2 (cut at 3): cost = 6 + solve(1,2) + solve(2,5). solve(1,2)=0. Need solve(2,5).

Step 5: solve(2, 5) — segment [3, 7], length = 4. Try k=3,4.

Step 6: Try k=3 (cut at 4): cost = 4 + solve(2,3) + solve(3,5). solve(2,3)=0. solve(3,5) = segment [4,7], try k=4 (cut at 5): cost = 3. So solve(2,5) via k=3 = 4 + 0 + 3 = 7.

Step 7: Try k=4 (cut at 5): cost = 4 + solve(2,4) + solve(4,5). solve(2,4) = segment [3,5], try k=3 (cut at 4): cost = 2. solve(4,5)=0. So solve(2,5) via k=4 = 4 + 2 + 0 = 6.

Step 8: solve(2,5) = min(7, 6) = 6. Going back: solve(1,5) via k=2 = 6 + 0 + 6 = 12.

Step 9: Continue exploring other k values for solve(1,5). After trying all: solve(1,5) = 12.

Step 10: Back to solve(0,5) with k=1: 7 + 0 + 12 = 19. Now try k=2 (cut at 3): 7 + solve(0,2) + solve(2,5).

Step 11: solve(0,2) = segment [0,3], try k=1 (cut at 1): cost = 3 + 0 + 0 = 3.

Step 12: solve(0,5) via k=2 = 7 + 3 + 6 = 16. Try remaining k values: k=3 gives 17, k=4 gives 17.

Step 13: solve(0,5) = min(19, 16, 17, 17) = 16.

Recursive Exploration of All Cutting Orders — Watch how the recursion tries every possible first cut for each segment, branching into sub-problems. Notice overlapping calls like solve(2,5) being computed multiple times.

Algorithm

  1. Add 0 and n to the cuts array as boundary markers.
  2. Sort the extended cuts array.
  3. Define solve(i, j) = minimum cost to make all cuts between indices i and j in the sorted array.
  4. Base case: If j - i ≤ 1, return 0 (no interior cut points in this segment).
  5. Recursive case: For each k from i+1 to j-1:
    • Try cutting at position cuts[k].
    • Cost = (cuts[j] - cuts[i]) + solve(i, k) + solve(k, j).
  6. Return the minimum cost across all choices of k.
  7. The answer is solve(0, m-1) where m is the length of the extended array.

Code

class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(0);
        cuts.push_back(n);
        sort(cuts.begin(), cuts.end());
        int m = cuts.size();
        return solve(cuts, 0, m - 1);
    }

private:
    int solve(vector<int>& cuts, int i, int j) {
        if (j - i <= 1) return 0;

        int best = INT_MAX;
        for (int k = i + 1; k < j; k++) {
            int cost = (cuts[j] - cuts[i]) + solve(cuts, i, k) + solve(cuts, k, j);
            best = min(best, cost);
        }
        return best;
    }
};
class Solution:
    def minCost(self, n: int, cuts: list[int]) -> int:
        cuts.extend([0, n])
        cuts.sort()
        m = len(cuts)

        def solve(i: int, j: int) -> int:
            if j - i <= 1:
                return 0
            best = float('inf')
            for k in range(i + 1, j):
                cost = (cuts[j] - cuts[i]) + solve(i, k) + solve(k, j)
                best = min(best, cost)
            return best

        return solve(0, m - 1)
class Solution {
    public int minCost(int n, int[] cuts) {
        int c = cuts.length;
        int[] ext = new int[c + 2];
        for (int i = 0; i < c; i++) ext[i] = cuts[i];
        ext[c] = 0;
        ext[c + 1] = n;
        Arrays.sort(ext);
        int m = ext.length;
        return solve(ext, 0, m - 1);
    }

    private int solve(int[] cuts, int i, int j) {
        if (j - i <= 1) return 0;
        int best = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; k++) {
            int cost = (cuts[j] - cuts[i]) + solve(cuts, i, k) + solve(cuts, k, j);
            best = Math.min(best, cost);
        }
        return best;
    }
}

Complexity Analysis

Time Complexity: O(2^m) — Exponential

Let m be the size of the extended cuts array (original cuts + 2 boundaries). At each recursive call for a segment with k interior cut points, we make k recursive branches. Without memoization, overlapping subproblems are recomputed. The total number of recursive calls grows exponentially. For m up to 102, this is completely infeasible.

Space Complexity: O(m)

The recursion stack depth is at most m (one level per cut point in the worst case). The sorted cuts array uses O(m) space.

Why This Approach Is Not Efficient

The brute force recursion is exponential because it recomputes the same sub-segments repeatedly. In our trace, solve(2,5) was computed multiple times — once from solve(1,5) and again from solve(0,5).

The total number of unique sub-problems is actually small: each sub-problem is defined by a pair (i, j) where 0 ≤ i < j ≤ m-1, giving at most m*(m-1)/2 ≈ 5000 unique pairs for m = 102. But the brute force doesn't remember results and recomputes them from scratch each time.

The fix is memoization: cache the result of solve(i, j) the first time it's computed, and return the cached value on subsequent calls. This transforms exponential time into polynomial time.

Better Approach - Top-Down Memoization

Intuition

The recursive structure from the brute force is correct — the problem is just redundant computation. We can fix this with a simple addition: a 2D memo table that remembers the answer for each (i, j) pair.

Before computing solve(i, j), check if we already have the answer. If yes, return it immediately. If not, compute it, store it, and then return. This is called top-down dynamic programming or memoization.

The recurrence stays the same:

  • solve(i, j) = 0 if j - i ≤ 1
  • solve(i, j) = min over all k in (i+1..j-1) of { (cuts[j] - cuts[i]) + solve(i, k) + solve(k, j) }

The only change is caching. Since there are O(m²) unique (i, j) pairs and each pair tries at most O(m) values of k, the total work is O(m³).

Step-by-Step Explanation

Same example: n = 7, cuts = [0, 1, 3, 4, 5, 7].

Step 1: Call solve(0, 5). Not in memo. Try all k values.

Step 2: k=1 → need solve(0,1) and solve(1,5). solve(0,1) = 0 (base case, cached).

Step 3: solve(1,5): not in memo. Try k=2 → need solve(1,2) and solve(2,5). solve(1,2) = 0 (cached).

Step 4: solve(2,5): not in memo. Try k=3 → need solve(2,3) and solve(3,5). Both not cached yet.

Step 5: solve(2,3) = 0. solve(3,5): try k=4 → 3 + 0 + 0 = 3. Cache solve(3,5) = 3.

Step 6: solve(2,5) via k=3: 4 + 0 + 3 = 7. Try k=4: need solve(2,4). solve(2,4) = 2 + 0 + 0 = 2 (cached). Then 4 + 2 + 0 = 6. Cache solve(2,5) = 6.

Step 7: Back in solve(1,5): k=2 gives 6 + 0 + 6 = 12. Try k=3: need solve(1,3) and solve(3,5). solve(3,5) = 3 from cache ← no recomputation!

Step 8: solve(1,3) = min over k=2: 3 + 0 + 0 = 3. Cache it. k=3: 6 + 3 + 3 = 12. Try k=4: need solve(1,4) and solve(4,5).

Step 9: solve(1,4): try k=2: 4 + 0 + solve(2,4) = 4 + 0 + 2 = 6. try k=3: 4 + solve(1,3) + 0 = 4 + 3 + 0 = 7. Cache solve(1,4) = 6. k=4: 6 + 6 + 0 = 12. Cache solve(1,5) = 12.

Step 10: Back in solve(0,5): k=1 → 7 + 0 + 12 = 19. k=2 → need solve(0,2) and solve(2,5). solve(2,5) = 6 from cache!

Step 11: solve(0,2): try k=1: 3 + 0 + 0 = 3. Cache it. k=2: 7 + 3 + 6 = 16.

Step 12: k=3: need solve(0,3). solve(0,3): try k=1: 4 + 0 + 3 = 7. try k=2: 4 + 3 + 0 = 7. Cache solve(0,3) = 7. k=3: 7 + 7 + 3 = 17.

Step 13: k=4: need solve(0,4). solve(0,4): try k=1: 5 + 0 + solve(1,4) = 5 + 0 + 6 = 11. try k=2: 5 + solve(0,2) + solve(2,4) = 5 + 3 + 2 = 10. try k=3: 5 + 7 + 0 = 12. Cache solve(0,4) = 10. k=4: 7 + 10 + 0 = 17.

Step 14: solve(0,5) = min(19, 16, 17, 17) = 16. Each sub-problem was computed once and cached.

Algorithm

  1. Add 0 and n to cuts, sort them. Let m = new length.
  2. Create a memo table dp[m][m] initialized to -1.
  3. Define solve(i, j):
    • If j - i ≤ 1, return 0.
    • If dp[i][j] ≠ -1, return dp[i][j] (cached result).
    • For each k from i+1 to j-1, compute cost = (cuts[j] - cuts[i]) + solve(i, k) + solve(k, j).
    • dp[i][j] = minimum cost across all k.
    • Return dp[i][j].
  4. Return solve(0, m-1).

Code

class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(0);
        cuts.push_back(n);
        sort(cuts.begin(), cuts.end());
        int m = cuts.size();
        vector<vector<int>> dp(m, vector<int>(m, -1));
        return solve(cuts, dp, 0, m - 1);
    }

private:
    int solve(vector<int>& cuts, vector<vector<int>>& dp, int i, int j) {
        if (j - i <= 1) return 0;
        if (dp[i][j] != -1) return dp[i][j];

        int best = INT_MAX;
        for (int k = i + 1; k < j; k++) {
            int cost = (cuts[j] - cuts[i]) + solve(cuts, dp, i, k) + solve(cuts, dp, k, j);
            best = min(best, cost);
        }
        return dp[i][j] = best;
    }
};
class Solution:
    def minCost(self, n: int, cuts: list[int]) -> int:
        cuts.extend([0, n])
        cuts.sort()
        m = len(cuts)
        memo = {}

        def solve(i: int, j: int) -> int:
            if j - i <= 1:
                return 0
            if (i, j) in memo:
                return memo[(i, j)]

            best = float('inf')
            for k in range(i + 1, j):
                cost = (cuts[j] - cuts[i]) + solve(i, k) + solve(k, j)
                best = min(best, cost)

            memo[(i, j)] = best
            return best

        return solve(0, m - 1)
class Solution {
    private int[][] dp;
    private int[] sortedCuts;

    public int minCost(int n, int[] cuts) {
        int c = cuts.length;
        sortedCuts = new int[c + 2];
        for (int i = 0; i < c; i++) sortedCuts[i] = cuts[i];
        sortedCuts[c] = 0;
        sortedCuts[c + 1] = n;
        Arrays.sort(sortedCuts);
        int m = sortedCuts.length;
        dp = new int[m][m];
        for (int[] row : dp) Arrays.fill(row, -1);
        return solve(0, m - 1);
    }

    private int solve(int i, int j) {
        if (j - i <= 1) return 0;
        if (dp[i][j] != -1) return dp[i][j];

        int best = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; k++) {
            int cost = (sortedCuts[j] - sortedCuts[i]) + solve(i, k) + solve(k, j);
            best = Math.min(best, cost);
        }
        return dp[i][j] = best;
    }
}

Complexity Analysis

Time Complexity: O(m³)

There are O(m²) unique (i, j) pairs. For each pair, we iterate over at most O(m) values of k. Total: O(m²) × O(m) = O(m³). With m ≤ 102, this is ≈ 10^6 operations — very fast.

Space Complexity: O(m²)

The memo table is m × m. The recursion stack depth is at most O(m). Total: O(m²).

Why This Approach Is Not Efficient

The memoization approach has the correct O(m³) time complexity and works perfectly. However, it uses recursion, which means:

  1. Stack overhead: Each recursive call adds a frame to the call stack. For deeply nested sub-problems, this can be significant.
  2. Function call overhead: Repeated function calls with cache lookups (hash map or array checks) add constant-factor overhead.
  3. Non-sequential memory access: The recursion explores sub-problems in a top-down order, which may not be cache-friendly.

The bottom-up tabulation approach eliminates recursion entirely by filling the DP table in a systematic order (from smaller intervals to larger ones). It has the same asymptotic complexity but better constant factors and no risk of stack overflow.

Optimal Approach - Bottom-Up Interval DP

Intuition

Instead of solving top-down with recursion, we fill the DP table bottom-up by processing intervals in order of increasing length. This is classic interval DP.

The key observation: to compute dp[i][j] (the minimum cost for a segment), we only need dp[i][k] and dp[k][j] for all k between i and j. Both of these represent shorter intervals. So if we process intervals from shortest to longest, all dependencies are already computed when we need them.

The algorithm:

  1. Prepare the sorted cuts array with boundaries: [0, 1, 3, 4, 5, 7].
  2. Intervals of length 1 (adjacent pairs like [0,1], [1,3]) have no interior cuts → cost = 0.
  3. Intervals of length 2 (like [0,3]) have exactly one cut point → we must make that cut.
  4. Build up to the full interval [0,7].

This eliminates recursion completely while computing the exact same values. It's also more cache-friendly because we access the 2D array in a predictable pattern.

Diagram showing how interval DP builds up from small segments to the full stick, with arrows showing dependencies
Diagram showing how interval DP builds up from small segments to the full stick, with arrows showing dependencies

Step-by-Step Explanation

Extended cuts: [0, 1, 3, 4, 5, 7] (m = 6). Build table dp[i][j].

Step 1: All intervals of length ≤ 1 have cost 0. These are the base cases: dp[0][1]=0, dp[1][2]=0, dp[2][3]=0, dp[3][4]=0, dp[4][5]=0.

Step 2: Length 2 intervals — dp[0][2]: segment [0,3]. Only cut at index 1 (position 1). dp[0][2] = dp[0][1] + dp[1][2] + (3-0) = 0 + 0 + 3 = 3.

Step 3: dp[1][3]: segment [1,4]. Only cut at index 2 (position 3). dp[1][3] = 0 + 0 + (4-1) = 3.

Step 4: dp[2][4]: segment [3,5]. Only cut at index 3 (position 4). dp[2][4] = 0 + 0 + (5-3) = 2.

Step 5: dp[3][5]: segment [4,7]. Only cut at index 4 (position 5). dp[3][5] = 0 + 0 + (7-4) = 3.

Step 6: Length 3 — dp[0][3]: segment [0,4]. Try k=1 and k=2.

  • k=1: dp[0][1] + dp[1][3] + 4 = 0 + 3 + 4 = 7.
  • k=2: dp[0][2] + dp[2][3] + 4 = 3 + 0 + 4 = 7.
  • dp[0][3] = min(7, 7) = 7.

Step 7: dp[1][4]: segment [1,5]. Try k=2, k=3.

  • k=2: dp[1][2] + dp[2][4] + 4 = 0 + 2 + 4 = 6.
  • k=3: dp[1][3] + dp[3][4] + 4 = 3 + 0 + 4 = 7.
  • dp[1][4] = 6.

Step 8: dp[2][5]: segment [3,7]. Try k=3, k=4.

  • k=3: dp[2][3] + dp[3][5] + 4 = 0 + 3 + 4 = 7.
  • k=4: dp[2][4] + dp[4][5] + 4 = 2 + 0 + 4 = 6.
  • dp[2][5] = 6.

Step 9: Length 4 — dp[0][4]: segment [0,5]. Try k=1,2,3.

  • k=1: 0 + 6 + 5 = 11.
  • k=2: 3 + 2 + 5 = 10.
  • k=3: 7 + 0 + 5 = 12.
  • dp[0][4] = 10.

Step 10: dp[1][5]: segment [1,7]. Try k=2,3,4.

  • k=2: 0 + 6 + 6 = 12.
  • k=3: 3 + 3 + 6 = 12.
  • k=4: 6 + 0 + 6 = 12.
  • dp[1][5] = 12.

Step 11: Length 5 — dp[0][5]: segment [0,7]. Try k=1,2,3,4.

  • k=1: 0 + 12 + 7 = 19.
  • k=2: 3 + 6 + 7 = 16.
  • k=3: 7 + 3 + 7 = 17.
  • k=4: 10 + 0 + 7 = 17.
  • dp[0][5] = 16. ✓

Bottom-Up Interval DP — Filling the Table from Small Intervals to Large — Watch the DP table fill from short intervals (adjacent cut points) up to the full stick. Each cell dp[i][j] tries all cut points k between i and j, choosing the minimum-cost split.

Algorithm

  1. Add 0 and n to the cuts array. Sort it. Let m = new length.
  2. Create a 2D table dp[m][m] initialized to 0.
  3. Iterate by interval length len from 2 to m-1:
    • For each starting index i from 0 to m - len - 1:
      • Set j = i + len.
      • Initialize dp[i][j] = infinity.
      • For each k from i+1 to j-1:
        • dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i])
  4. Return dp[0][m-1].

Code

class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(0);
        cuts.push_back(n);
        sort(cuts.begin(), cuts.end());
        int m = cuts.size();

        vector<vector<int>> dp(m, vector<int>(m, 0));

        for (int len = 2; len < m; len++) {
            for (int i = 0; i + len < m; i++) {
                int j = i + len;
                dp[i][j] = INT_MAX;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = min(dp[i][j],
                        dp[i][k] + dp[k][j] + cuts[j] - cuts[i]);
                }
            }
        }

        return dp[0][m - 1];
    }
};
class Solution:
    def minCost(self, n: int, cuts: list[int]) -> int:
        cuts.extend([0, n])
        cuts.sort()
        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] = 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]
class Solution {
    public int minCost(int n, int[] cuts) {
        int c = cuts.length;
        int[] ext = new int[c + 2];
        for (int i = 0; i < c; i++) ext[i] = cuts[i];
        ext[c] = 0;
        ext[c + 1] = n;
        Arrays.sort(ext);
        int m = ext.length;

        int[][] dp = new int[m][m];

        for (int len = 2; len < m; len++) {
            for (int i = 0; i + len < m; i++) {
                int j = i + len;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j],
                        dp[i][k] + dp[k][j] + ext[j] - ext[i]);
                }
            }
        }

        return dp[0][m - 1];
    }
}

Complexity Analysis

Time Complexity: O(m³)

Where m = cuts.length + 2 (after adding boundaries). The three nested loops (length, starting index, split point k) give O(m³). With cuts.length ≤ 100, m ≤ 102, so m³ ≈ 1,061,208 — very fast, well under typical time limits.

Space Complexity: O(m²)

The 2D DP table is m × m. With m ≤ 102, this is about 10,404 integers — negligible memory.

This is the optimal approach for this problem. The time complexity is driven by the O(m) choices at each of the O(m²) intervals. No known algorithm improves upon this for the general case, though Knuth's optimization can sometimes reduce to O(m²) for specific interval DP problems (not applicable here in the standard formulation).