Minimum Cost to Cut a Stick — Hard Problem & Solution

A stick of length n is marked at the positions in cuts. Cutting a stick costs the length of the stick being cut, and after a cut the two pieces are cut…

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Sorting
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A stick of length n is marked at the positions in cuts. Cutting a stick costs the length of the stick being cut, and after a cut the two pieces are cut independently.

You may perform the cuts in any order. Return the minimum total cost.

Example 1

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Cutting in the order 3, 5, 1, 4 costs 7 + 4 + 3 + 2.

Example 2

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

Example 3

Input: n = 5, cuts = [2]
Output: 5
Explanation: One cut on the whole stick.

Constraints

2 <= n <= 1000000
1 <= cuts.length <= 100
1 <= cuts[i] <= n - 1
All values in cuts are distinct.

How to solve Minimum Cost to Cut a Stick

Interval DP over the sorted cut positions. Once a piece is isolated, the cuts inside it never interact with anything outside — so deciding which of its cuts happens first splits the problem cleanly.

Approach

Build pts = [0] + sorted(cuts) + [n].
dp[i][j] is the minimum cost to make every cut strictly between pts[i] and pts[j].
For each k in (i, j), cutting at pts[k] first costs pts[j] - pts[i] plus dp[i][k] + dp[k][j].
Fill by increasing interval length; the answer is dp[0][m-1].

Why it works

The cost of any single cut is the length of the piece it lands on, which depends only on the two nearest cuts already made on either side — exactly the interval boundaries. So fixing the first cut inside an interval makes the two halves independent, which is what licenses the DP. Adding the sentinels removes the need to special-case the stick's ends.

Complexity

Time — O(m³) where m is the number of cuts
Space — O(m²)

Pitfalls

Choosing which cut is made last does not decompose — the piece's length would then depend on cuts outside the interval.
The cuts must be sorted; the input order is arbitrary.
A greedy 'always cut in the middle' is wrong.

Reference solution

Python

from typing import List

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

JavaScript

var minCost = function(n, cuts) {
    var pts = [0].concat(cuts.slice().sort(function(a, b) { return a - b; })).concat([n]);
    var m = pts.length;
    var dp = [];
    for (var a = 0; a < m; a++) {
        var row = [];
        for (var b = 0; b < m; b++) row.push(0);
        dp.push(row);
    }
    for (var len = 2; len < m; len++) {
        for (var i = 0; i + len < m; i++) {
            var j = i + len;
            var best = Infinity;
            for (var k = i + 1; k < j; k++) {
                var v = dp[i][k] + dp[k][j];
                if (v < best) best = v;
            }
            dp[i][j] = best + pts[j] - pts[i];
        }
    }
    return dp[0][m - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue