Topics › Dynamic Programming › MCM DP - Partition DP

Minimum cost to cut the stick

Hard TUF ID 328 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

A wooden stick of length n is marked at positions 0 to n. You must make a cut at every position listed in cuts (distinct values between 1 and n - 1), in any order you like. Each cut splits one piece into two, and costs the current length of the piece being cut. Return the minimum total cost.

Constraints (LeetCode 1547): 2 ≤ n ≤ 10^6, 1 ≤ cuts.length ≤ min(n - 1, 100), all cut positions distinct. The Java methods also accept an empty cuts array.

Example 1

n = 7, cuts = [1, 3, 4, 5]
answer = 16      // order 3, 5, 1, 4 costs 7 + 4 + 3 + 2

Cutting in the given order 1, 3, 4, 5 would cost 7 + 6 + 4 + 3 = 20: the long right piece is paid for again and again.

Example 2

n = 9, cuts = [5, 6, 1, 4, 2]
answer = 22      // for example, cut 4 first (9), then 2 (4), then 6 (5), then 1 (2) and 5 (2)

Seeing the partition structure

Suppose that on some piece [a, b] the first cut is made at position p. It costs b - a, the full piece, and leaves two pieces [a, p] and [p, b]. From then on the two pieces never interact: every remaining cut lies inside exactly one of them, and a cut inside [a, p] never changes the length of [p, b]. So the best total for [a, b] is b - a plus the best total for each half, minimised over the choice of p. This is the matrix chain shape: a range, a split point, two independent sub-ranges, and a cost that depends only on the range ends.

To make “the cuts inside a piece” a contiguous block of indices, sort the cuts and add the two stick ends. With c = [0, sorted cuts..., n], a piece is described by two indices i < j into c, and the cuts inside it are exactly c[i + 1] .. c[j - 1]. The recurrence is

f(i, j) = 0                                       if j - i < 2   (no cut strictly inside)
f(i, j) = (c[j] - c[i]) + min over i < k < j of  f(i, k) + f(k, j)
answer  = f(0, m - 1)       where m = cuts.length + 2

Striver’s version indexes the cuts themselves (f(i, j) for cuts i..j, piece length c[j + 1] - c[i - 1]); it is the same recurrence with indices shifted by one. Note also that the state uses indices into the cut list, not positions on the stick. That keeps the table at most 102 × 102 even when n is a million.

Approach 1: Recursion

Intuition. Implement the recurrence directly. For the piece between c[i] and c[j], try every cut inside as the first one; the cut itself pays for the whole piece, and the two halves are solved recursively.

Algorithm.

1. Build c with withEnds: copy the cuts, add 0 and n, sort the middle part.
2. If j - i < 2, there is nothing to cut; return 0.
3. Otherwise return c[j] - c[i] plus the minimum over k of f(i, k) + f(k, j).

static int[] withEnds(int n, int[] cuts) {
    int m = cuts.length;
    int[] c = new int[m + 2];
    for (int i = 0; i < m; i++) c[i + 1] = cuts[i];
    c[m + 1] = n;                                           // c[0] = 0 already
    Arrays.sort(c, 1, m + 1);
    return c;
}

static int recursive(int n, int[] cuts) {
    int[] c = withEnds(n, cuts);
    return solve(0, c.length - 1, c);
}

static int solve(int i, int j, int[] c) {
    if (j - i < 2) return 0;                                // no cut strictly between c[i] and c[j]
    int best = Integer.MAX_VALUE;
    for (int k = i + 1; k < j; k++) {                       // cut at c[k] first, then solve both halves
        best = Math.min(best, solve(i, k, c) + solve(k, j, c));
    }
    return best + c[j] - c[i];                              // the first cut pays for the whole piece
}

Complexity. Time exponential in the number of cuts: the recursion explores every order of cutting, up to the symmetry of independent pieces, which is a Catalan-sized family. Space O(m) for the recursion depth.

Approach 2: Memoization

Intuition. Different cutting orders lead to the same pieces. For example, the piece [3, 5] is reached whether we cut 3 first or 5 first. There are only O(m^2) pairs (i, j), so cache each answer. Costs are non-negative, so -1 marks “not computed”.

Algorithm.

1. Build c, create dp[m][m] filled with -1.
2. Same recursion, but return the cached value when present and store each result.

static int memoization(int n, int[] cuts) {
    int[] c = withEnds(n, cuts);
    int[][] dp = new int[c.length][c.length];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(0, c.length - 1, c, dp);
}

static int memo(int i, int j, int[] c, int[][] dp) {
    if (j - i < 2) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    int best = Integer.MAX_VALUE;
    for (int k = i + 1; k < j; k++) best = Math.min(best, memo(i, k, c, dp) + memo(k, j, c, dp));
    return dp[i][j] = best + c[j] - c[i];
}

Complexity. Time O(m^3): O(m^2) states, each trying O(m) first cuts. With at most 100 cuts that is about a million steps. Space O(m^2).

Approach 3: Tabulation

Intuition. dp[i][j] reads dp[i][k] (same row, k < j) and dp[k][j] (lower row, k > i). So fill rows from the bottom up and each row from left to right. Cells with j = i + 1 stay 0: a piece with no cut inside costs nothing. The first useful row is i = m - 3, whose only cell j = m - 1 contains one cut.

Algorithm.

1. Build c and allocate dp[m][m] (zeros).
2. For i from m - 3 down to 0, for j from i + 2 to m - 1: dp[i][j] = c[j] - c[i] + min(dp[i][k] + dp[k][j]).
3. Return dp[0][m - 1].

static int tabulation(int n, int[] cuts) {
    int[] c = withEnds(n, cuts);
    int m = c.length;
    int[][] dp = new int[m][m];                             // dp[i][i + 1] = 0: nothing to cut
    for (int i = m - 3; i >= 0; i--) {
        for (int j = i + 2; j < m; j++) {
            int best = Integer.MAX_VALUE;
            for (int k = i + 1; k < j; k++) best = Math.min(best, dp[i][k] + dp[k][j]);
            dp[i][j] = best + c[j] - c[i];
        }
    }
    return dp[0][m - 1];
}

Dry run on Example 1: c = [0, 1, 3, 4, 5, 7], so m = 6. Some intermediate cells:

The final cell dp[0][5] (the whole stick, length 7) tries each first cut:

Complexity. Time O(m^3), space O(m^2). As with matrix chain multiplication, the table cannot be reduced to one row, because each cell reads an entire row segment and an entire column segment.

Edge cases and pitfalls

• Unsorted cuts. Without sorting, the cuts inside a piece are not a contiguous index range and the recurrence breaks. Example 2 is deliberately unsorted. The methods sort a copy, so the caller’s array is not modified.
• Forgetting the ends. Adding 0 and n lets the first cut cost n naturally; without them the length of the outer piece is unknown.
• No cuts. m = 2, nothing is inside [0, n], and the answer is 0.
• State size. A DP over stick positions would need 10^6 × 10^6 cells. The state must be indices into the cut list.
• Greedy fails. Cutting closest to the middle first is tempting but wrong: for n = 26, cuts = [1, 10, 14, 18] it cuts 14 first and pays 62, while the optimum is 60. The Java file tests that case and cross-checks all methods on 200 seeded random sticks.
• Overflow. At most 100 cuts each costing at most 10^6 stays below 10^8, so int is enough.

Related problems

• Matrix chain multiplication is the original split-a-range recurrence.
• Matrix Chain Multiplication - Bottom-Up - (DP-49) explains the fill order of such tables in detail.
• Burst balloons uses the same padded array with sentinel ends.
• Minimum Cost to Connect Sticks looks similar, but there any two sticks may be joined, so a greedy heap works; here the cut positions fix the structure.
• Palindrome partitioning II is another partition DP with a simpler one-dimensional state.