Minimum Cost to Cut a Stick

Hard25–30 min

Topics

Dynamic ProgrammingInterval DP

Companies

AmazonGoogleBloomberg

A wooden stick of length `n` needs a cut made at every position listed in `cuts`. Making a cut costs the length of whichever piece it's currently slicing, and once a piece is cut it splits into two independent pieces that each keep needing their own remaining cuts. The order the cuts happen in changes the total cost, because an early cut on a long, still-uncut stick is expensive, while the same cut made later — after the stick around it has already been chopped down — is cheap. Find the order that minimizes the total. The trick is to stop thinking about cut *order* and instead think about cut *positions*. Sort every requested cut position together with the two ends of the stick (0 and n) into one list of boundary points. Any stretch of stick between two of those points, once every point strictly inside it has been cut, never needs to be touched again — so the cheapest way to finish that stretch depends only on its two endpoints, not on how it was reached. That cost is the stretch's current length (paid once, by whichever cut happens last inside it) plus the cost of finishing whatever's left on each side of that final cut — and trying every possible "last cut" position finds the cheapest one.

Test Case 1:

Input:n = 8, cuts = [1,7]

Output:15

Explanation:Whichever cut is made first, the stick is still full-length (8) for that cut. Cutting at 1 first costs 8, then finishing the [1,8] piece at 7 costs 7 more — 15 total. Cutting at 7 first gives the identical total by symmetry.

Test Case 2:

Input:n = 1, cuts = []

Output:0

Explanation:No cuts requested — the stick is left whole, so there's nothing to pay for.

Test Case 3:

Input:n = 10, cuts = [5]

Output:10

Explanation:A single cut always costs the full current stick length, since it's the only cut and the stick hasn't been touched yet.

Constraints

◆1 ≤ n ≤ 30
◆0 ≤ cuts.length ≤ 6
◆1 ≤ cuts[i] < n, all cuts distinct

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Try Every Cut Order

Brute

Whichever cut happens first inside a segment splits that segment into two independent smaller segments, and the remaining cuts sort themselves into "belongs to the left piece" or "belongs to the right piece" automatically, since a cut position can only ever fall on one side of wherever the first cut landed. Trying every remaining cut as the "first one made" in the current segment, and recursing into both halves, is correct — but the same segment can be reached again later through a completely different sequence of earlier cuts, and gets solved again from scratch each time with no memory of the answer.

TimeO(n · 2ⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    public int minCost(int n, int[] cuts) {
        List<Integer> remaining = new ArrayList<>();
        for (int c : cuts) remaining.add(c);
        return solve(0, n, remaining);
    }
    private int solve(int left, int right, List<Integer> remaining) {
        int best = Integer.MAX_VALUE;
        boolean any = false;
        for (int i = 0; i < remaining.size(); i++) {
            int c = remaining.get(i);
            if (c <= left || c >= right) continue;
            any = true;
            List<Integer> rest = new ArrayList<>(remaining);
            rest.remove(i);
            int cost = (right - left) + solve(left, c, rest) + solve(c, right, rest);
            if (cost < best) best = cost;
        }
        return any ? best : 0;
    }
}

Optimal — Interval DP Over Sorted Cut Points

Optimal

Instead of tracking which cuts remain out of the original list, sort every cut position together with the two natural boundaries 0 and n into one array of "points." Any two neighboring points in that sorted array bound a stretch of stick that will never need to be cut again once every point between them has been used — so dp[i][j] can mean "cheapest way to finish all the cuts strictly between point i and point j." That cost is the current length (points[j] − points[i]) for whichever cut happens last in that stretch, plus the cost of finishing its two sides — dp[i][k] and dp[k][j] — for whichever split point k turns out cheapest. Filling in shorter stretches before longer ones means every dp[i][k] and dp[k][j] a bigger stretch needs is already sitting there.

TimeO(m³)

SpaceO(m²)