Problem 32.5 · Advanced DPHard

Minimum Cost to Cut a Stick

What it teaches: Interval DP over cut positions: each cut costs the current segment's length.

Practise it on judges as “Minimum Cost to Cut a Stick”.

The problem

A stick of length n must be cut at every position in cuts, in any order. Each cut costs the length of the piece being cut. Return the minimum total cost.

Example 1

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

Constraints

2 ≤ n ≤ 10⁶
1 ≤ cuts ≤ 100

Pattern clues in the wording

→ Order of operations changes the cost
→ Few positions

These clues point to Interval DP: dp[i][j] is the answer for the range i..j, built from smaller ranges by trying every split point.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int minCost(int n, int[] cuts) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 7 cuts = [1,3,4,5]	16
2	n = 9 cuts = [5,6,1,4,2]	22

From slow to fast

Approaches

1. Interval DP on positions · O(m³) for m cuts

Interval DP on positions

Time O(m³) for m cuts Space O(m²)

dp[i][j] = (c[j] − c[i]) + min over i < k < j of dp[i][k] + dp[k][j]; 0 when no cut lies between.

Approach 1

import java.util.Arrays;

class Solution {
    public int minCost(int n, int[] cuts) {
        int m = cuts.length + 2;
        int[] c = new int[m];
        c[0] = 0;
        c[m - 1] = n;
        int[] sorted = cuts.clone();
        Arrays.sort(sorted);
        for (int i = 0; i < sorted.length; i++) c[i + 1] = sorted[i];
        int[][] dp = new int[m][m];
        for (int gap = 2; gap < m; gap++)
            for (int i = 0; i + gap < m; i++) {
                int j = i + gap;
                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]);
                dp[i][j] += c[j] - c[i];
            }
        return dp[0][m - 1];
    }
}

Verdict: Independent of n.

Before you submit

Edge cases and common mistakes

Test these inputs

One cut (cost n)
Unsorted cuts

Mistakes people make

Making the DP depend on n (10⁶) instead of the cut count.

Interview

Follow-up questions

How is this like building an optimal binary search tree?

Command Palette

The problem

Approaches

Interval DP on positions

Edge cases and common mistakes

Follow-up questions