DSA Minimum Cost to Cut a Stick

The problem

Minimum Cost to Cut a Stick asks for the cheapest order in which to make a set of cuts in one stick. The stick runs from position 0 to position n. Every cut position must be cut exactly once.

One cut charges the full length of the piece it splits. A cut made early, while its piece is still long, charges more than the same cut made late. The order is the whole problem.

cases = [
    (7, [1, 3, 5], 14),
    (7, [1, 3, 4, 5], 16),
    (9, [2, 5, 7], 18),
    (6, [], 0),
]
for n, cuts, expected in cases:
    print("stick", n, "cuts", cuts, "cheapest total:", expected)

Read one row at a time. The first row needs three cuts and pays 14 at best. The last row needs no cuts at all, so it pays nothing.

Intuition: cut from left to right

The first idea cuts in position order, from the left end to the right end. The order is easy to name. It is also easy to beat.

Cutting left to right makes the first cut pay for the whole stick. Each later cut then pays for a piece that is still long, because the cuts to its right have not happened yet.

def cost_of_order(n, order):
    pieces = [(0, n)]
    total = 0
    for cut in order:
        for i, (lo, hi) in enumerate(pieces):
            if lo < cut < hi:
                total += hi - lo
                pieces[i:i + 1] = [(lo, cut), (cut, hi)]
                break
    return total

print("order 1, 3, 5 costs:", cost_of_order(7, [1, 3, 5]))
print("order 3, 1, 5 costs:", cost_of_order(7, [3, 1, 5]))
print("order 5, 3, 1 costs:", cost_of_order(7, [5, 3, 1]))

The middle order wins on this stick. Cutting at 3 first splits the stick into two short pieces. Both later cuts then charge short lengths.

Brute force: try every first cut, recursively

The brute force picks the first cut of a piece in every possible way. Each choice splits the piece in two. The two halves are then solved the same way, with no memory of earlier work.

A counter records the calls. The same small piece is solved again and again, once for every path that reaches it.

calls = 0

def brute(points, i, j):
    global calls
    calls += 1
    if j - i < 2:
        return 0
    best = None
    for k in range(i + 1, j):
        cand = brute(points, i, k) + brute(points, k, j) + (points[j] - points[i])
        if best is None or cand < best:
            best = cand
    return best

points = sorted([0, 7] + [1, 3, 5])
print("cheapest:", brute(points, 0, len(points) - 1), "calls:", calls)
calls = 0
points = sorted([0, 7] + [1, 3, 4, 5])
print("cheapest:", brute(points, 0, len(points) - 1), "calls:", calls)

Both answers are correct. The call count is the problem. Four cuts already need dozens of calls, and most of them repeat work on pieces already solved.

The optimal solution: fill a table over ranges

The state is a range between two boundary points, and the table entry for a range holds the cheapest cost of cutting inside it once every first cut for that range has been tried. That one state is the whole method.

The boundary points are the stick ends plus every cut, sorted. A range with no cut inside it costs zero. Longer ranges are filled after shorter ones, so both halves of any split are ready when needed.

def cheapest_cuts(n, cuts):
    points = sorted([0, n] + cuts)
    m = len(points)
    table = [[0] * m for _ in range(m)]
    choice = [[None] * m for _ in range(m)]
    for length in range(2, m):
        for i in range(m - length):
            j = i + length
            best = None
            for k in range(i + 1, j):
                cand = table[i][k] + table[k][j] + (points[j] - points[i])
                if best is None or cand < best:
                    best = cand
                    choice[i][j] = k
            table[i][j] = best

    def plan(i, j):
        k = choice[i][j]
        if k is None:
            return []
        return [points[k]] + plan(i, k) + plan(k, j)

    return table[0][m - 1], plan(0, m - 1)

cases = [
    (7, [1, 3, 5], 14),
    (7, [1, 3, 4, 5], 16),
    (9, [2, 5, 7], 18),
    (6, [], 0),
]
for n, cuts, expected in cases:
    total, order = cheapest_cuts(n, cuts)
    print("stick", n, "cuts", sorted(cuts), "-> total", total, "order", order, "match:", total == expected)

Every case from the first section matches. The table also records one first cut per range, so a cheapest order is read back out, not just a cheapest total.

Walkthrough: stick 7 with cuts at 1, 3 and 5

The walk fills the table for points 0, 1, 3, 5 and 7. Ranges of one step cost zero. Longer ranges combine two shorter ones plus their own length.

points = [0, 1, 3, 5, 7]
m = len(points)
table = [[0] * m for _ in range(m)]
choice = [[None] * m for _ in range(m)]
for length in range(2, m):
    for i in range(m - length):
        j = i + length
        best = None
        for k in range(i + 1, j):
            cand = table[i][k] + table[k][j] + (points[j] - points[i])
            if best is None or cand < best:
                best = cand
                choice[i][j] = k
        table[i][j] = best
        print("range", points[i], "to", points[j], "first cut", points[choice[i][j]], "cost", best)
print("full stick cost:", table[0][m - 1])

The full range tries first cuts at 1, 3 and 5. Cutting at 3 first charges 7, then the left piece costs 3 and the right piece costs 4. The total 14 is read off the last row of the walk.

Complexity

For m boundary points the table holds one entry per pair of points, and each entry tries every cut inside its range, so the time is O(m^3). The table and the choice table each hold one entry per pair, so the space is O(m^2).

for cuts_count in [3, 4, 5, 6]:
    m = cuts_count + 2
    tried = 0
    for length in range(2, m):
        for i in range(m - length):
            j = i + length
            tried += j - i - 1
    print("cuts", cuts_count, "ranges", m * (m - 1) // 2, "first-cut tries", tried)

The try count grows much faster than the cut count. Six cuts need 56 first-cut tries in the table, against a far larger repeated count in the recursion.

Edge cases and pitfalls

No cuts means no cost, and one cut always charges the whole stick. Unsorted input is sorted before anything else runs, so the caller may pass cuts in any order.

The classic mistake charges the cut position instead of the piece length. A cut at 3 in a piece from 0 to 7 charges 7, not 3. The code below shows both numbers side by side.

def cheapest_total(n, cuts):
    points = sorted([0, n] + cuts)
    m = len(points)
    table = [[0] * m for _ in range(m)]
    for length in range(2, m):
        for i in range(m - length):
            j = i + length
            table[i][j] = min(
                table[i][k] + table[k][j] + (points[j] - points[i])
                for k in range(i + 1, j)
            )
    return table[0][m - 1]

print("no cuts:", cheapest_total(6, []))
print("one cut:", cheapest_total(6, [2]))
print("unsorted cuts:", cheapest_total(7, [5, 1, 3]))
print("neighbouring cuts:", cheapest_total(4, [1, 2, 3]))
print("wrong charge for cut at 3 in 0..7 would be:", 3)
print("right charge for cut at 3 in 0..7 is:", 7 - 0)

Neighbouring cuts still work. Each tiny piece charges its own small length, and no range is ever skipped.