Interval DP: merging and cutting costs

Interval dynamic programming solves problems about a row of things, such as marks on a log, stacks in a line or matrices in a product, where the answer for the stretch from position i to position j is built from the answers for shorter stretches inside it. The state is the pair (i, j). The move that makes it work is to fix one operation inside the stretch, the first cut or the last merge, because once it is fixed the parts on its two sides no longer affect each other, and each is a shorter stretch with an answer of its own. Fill dp[i][j] in order of increasing length, so that every shorter stretch is finished before it is read. With n items there are about n²/2 stretches and up to n choices for each, so most interval DPs cost O(n³).

This lesson solves two problems in full: cutting a log, with a brute force to check against, a table, a dry run, a proof and code in five languages, and binding stacks of pages, where the operation to fix is the last one. Then it shows how to recognise the pattern, how to rebuild the plan behind the number, and a bound on the split that turns O(n³) into O(n²), measured.

When a problem is interval DP

Three signals usually appear together:

• The input is a row, and every operation acts on a contiguous piece of it: cutting a piece in two, joining two neighbours, removing an item so that its neighbours touch.
• The cost of an operation depends on the piece it acts on, such as its length, its total or the values at its ends. The order of the operations then changes the total, so a greedy rule is suspect until proved.
• The limits are small: n in the tens or hundreds, because the usual solution tries every split of every piece.

The question to ask is what stays independent. If, after one operation inside a piece, the left part and the right part can be solved without looking at each other, the piece is a state and the operation is the choice. If the pieces need not stay contiguous, as when any two stacks of a row may be joined, the problem is a different one, and this lesson meets one of those too.

A problem solved in full: cutting a log

Examples that every version below prints:

• A log of 20 with marks at 6, 9 and 12 costs 38: cut at 12 first (20 credits), then at 6 (the piece of 12 that is left, 12 credits), then at 9 (a piece of 6, 6 credits).
• A log of 10 with marks at 2, 4 and 7 costs 20.
• A log of 7 with no marks costs 0, and with one mark at 3 it costs 7.
• 100 marks on a log of 1,000,000 cost 6,699,201.

The brute force: price every order

Three marks can be cut in 3! = 6 orders. Pricing an order is a simulation: keep the list of pieces, find the piece each cut falls on, add its length, and replace it by its two halves.

"""Every order of the cuts, priced: the brute force for cutting a log."""
from itertools import permutations
from math import factorial


def order_cost(length, order):
    """What making the cuts in this order costs: each cut costs the length of the piece it falls on."""
    pieces = [(0, length)]
    total = 0
    for c in order:
        for i, (a, b) in enumerate(pieces):
            if a < c < b:
                total += b - a
                pieces[i : i + 1] = [(a, c), (c, b)]
                break
    return total


def min_cut_cost_brute(length, cuts):
    return min(order_cost(length, order) for order in permutations(cuts))


def middle_first(length, cuts):
    """A greedy guess: on every piece, first cut at the mark nearest the piece's middle."""

    def plan(a, b, marks):
        if not marks:
            return 0
        k = min(marks, key=lambda c: abs(2 * c - (a + b)))
        return (b - a) + plan(a, k, [c for c in marks if c < k]) + plan(k, b, [c for c in marks if c > k])

    return plan(0, length, sorted(cuts))


for order in permutations([6, 9, 12]):
    print("cut at", *order, "-> costs", order_cost(20, order))
print("brute force, length 20, cuts 6 9 12 ->", min_cut_cost_brute(20, [6, 9, 12]))
print("middle first, same log ->", middle_first(20, [6, 9, 12]))
print("brute force, length 10, cuts 2 4 7 ->", min_cut_cost_brute(10, [2, 4, 7]))
for m in (8, 12, 20):
    print(f"{m} cuts: {factorial(m):,} orders")
print(f"100 cuts: a number of orders {len(str(factorial(100)))} digits long")

cut at 6 9 12 -> costs 45
cut at 6 12 9 -> costs 40
cut at 9 6 12 -> costs 40
cut at 9 12 6 -> costs 40
cut at 12 6 9 -> costs 38
cut at 12 9 6 -> costs 41
brute force, length 20, cuts 6 9 12 -> 38
middle first, same log -> 40
brute force, length 10, cuts 2 4 7 -> 20
8 cuts: 40,320 orders
12 cuts: 479,001,600 orders
20 cuts: 2,432,902,008,176,640,000 orders
100 cuts: a number of orders 158 digits long

The six orders cost between 38 and 45, and only one of them, 12 then 6 then 9, reaches 38. The run also tries a rule that sounds sensible, cutting every piece at the mark nearest its middle, and gets 40: it cuts at 9 first, because 9 is closest to the middle of the log, and each of the two pieces it leaves still needs a cut. The brute force is the reference for everything faster, and it is hopeless at the stated size: 12 marks already have 479,001,600 orders, and the number of orders of 100 marks is 158 digits long.

What to notice

Look at the first cut on the whole log. Whichever mark it uses, it costs the full length of the log, and afterwards the two pieces are separate logs: no cut on the left piece changes the price of any cut on the right one. So the cheapest plan for the whole log is its length plus the cheapest plans for the two pieces, for the best choice of the first mark. The pieces that ever appear are stretches between two marks, so add the two ends of the log to the list as marks of their own, the sentinels, and number the marks 0 to m + 1. Every piece is then a pair of mark numbers (i, j).

That gives the recurrence. Let best(i, j) be the cheapest way to make every cut strictly between marks i and j. If no mark lies between them it is 0; otherwise

where x is the list of mark positions. The price of the first cut, $x_j - x_i$, is the same for every k, so it sits outside the minimum; the choice of k only decides which two pieces are left.

Memoise first

The recurrence is already a program. With functools.cache around it, each pair (i, j) is worked out once, and the cache counts the work:

from functools import cache


def min_cut_cost(length, cuts):
    marks = [0, *sorted(cuts), length]  # the two ends of the log are marks too: the sentinels

    @cache
    def best(i, j):
        """The cheapest way to make every cut strictly between marks i and j."""
        if j - i < 2:
            return 0  # no mark between them: nothing to cut
        return marks[j] - marks[i] + min(best(i, k) + best(k, j) for k in range(i + 1, j))

    answer = best(0, len(marks) - 1)
    info = best.cache_info()
    print(f"  pieces worked out: {info.currsize}, answers reused: {info.hits}")
    return answer


print("length 20, cuts 6 9 12 ->", min_cut_cost(20, [6, 9, 12]))
print("length 10, cuts 2 4 7 ->", min_cut_cost(10, [2, 4, 7]))
print("length 7, no cuts ->", min_cut_cost(7, []))
print("length 7, one cut at 3 ->", min_cut_cost(7, [3]))
print("length 100, cuts every 10 ->", min_cut_cost(100, list(range(10, 100, 10))))

  pieces worked out: 10, answers reused: 11
length 20, cuts 6 9 12 -> 38
  pieces worked out: 10, answers reused: 11
length 10, cuts 2 4 7 -> 20
  pieces worked out: 1, answers reused: 0
length 7, no cuts -> 0
  pieces worked out: 3, answers reused: 0
length 7, one cut at 3 -> 7
  pieces worked out: 55, answers reused: 276
length 100, cuts every 10 -> 340

Three marks make five marks with the sentinels, and the cache holds 10 pieces, one for every pair i < j: that is every state there is. The evenly marked log of 100, with 9 marks, has 55 states and reuses a stored answer 276 times. The recursion goes at most one level deeper per mark, so 100 marks need about 100 nested calls, far below CPython’s default recursion limit of 1,000 that the lesson on recursion and DP measured.

Tabulate by length

A piece reads only pieces that are strictly shorter, so a loop over the gap j − i, from 2 upwards, fills the table in an order where everything it reads is finished. The table version also records, for every piece, the mark it is cut at first, which is what the plan needs:

def cut_table(length, cuts):
    """best[i][j]: the cheapest way to cut the piece between marks i and j; first[i][j]: the mark it is cut at first."""
    marks = [0, *sorted(cuts), length]
    n = len(marks)
    best = [[0] * n for _ in range(n)]
    first = [[None] * n for _ in range(n)]
    for gap in range(2, n):  # shorter pieces first, so every piece a step reads is finished
        for i in range(n - gap):
            j = i + gap
            k = min(range(i + 1, j), key=lambda k: best[i][k] + best[k][j])
            best[i][j] = marks[j] - marks[i] + best[i][k] + best[k][j]
            first[i][j] = k
    return marks, best, first


def plan(marks, first, i, j):
    """An order the saw can follow: the piece's first cut, then every cut of its left part, then of its right part."""
    k = first[i][j]
    if k is None:
        return []
    return [marks[k], *plan(marks, first, i, k), *plan(marks, first, k, j)]


marks, best, first = cut_table(20, [6, 9, 12])
print("marks:", *marks)
for gap in range(2, len(marks)):
    for i in range(len(marks) - gap):
        j = i + gap
        print(f"piece {marks[i]:>2} to {marks[j]:<2}  first cut at {marks[first[i][j]]:>2}  cost {best[i][j]:>2}")
print("order of cuts:", *plan(marks, first, 0, len(marks) - 1))

marks: 0 6 9 12 20
piece  0 to 9   first cut at  6  cost  9
piece  6 to 12  first cut at  9  cost  6
piece  9 to 20  first cut at 12  cost 11
piece  0 to 12  first cut at  6  cost 18
piece  6 to 20  first cut at 12  cost 20
piece  0 to 20  first cut at 12  cost 38
order of cuts: 12 6 9

Here is the same dry run, with the marks 0, 6, 9, 12 and 20 numbered 0 to 4, in the order the loop fills the pieces. Pieces with no mark inside cost 0 and are left out; each try is a first cut, then the costs of the two pieces it leaves.

• Gap 2. The piece 0–9 can only be cut at 6, for 9; the piece 6–12 at 9, for 6; and the piece 9–20 at 12, for 11.
• Gap 3. The piece 0–12 tries 6 (0 + 6) and 9 (9 + 0) and cuts at 6, for 12 + 6 = 18. The piece 6–20 tries 9 (0 + 11) and 12 (6 + 0) and cuts at 12, for 14 + 6 = 20.
• Gap 4. The whole log tries 6 (0 + 20), 9 (9 + 11) and 12 (18 + 0) and cuts at 12, for 20 + 18 = 38.

Why it is correct

Every plan for a piece starts with one cut, at some mark k, which costs the length of the piece. After it, the plan is a plan for the left part and a plan for the right part, interleaved in some order, and interleaving changes nothing because no cut on one part touches the other. So the cost of any plan is the length of the piece plus the costs of two plans for the two parts, and replacing either of those by the cheapest plan for its part can only lower the total. The cheapest plan with first cut k therefore costs the length plus best(i, k) plus best(k, j), and taking the best k covers every plan there is.

The loop keeps an invariant: before the step for gap g, every entry for a gap below g holds the cheapest cost of its piece. Gaps 0 and 1 hold 0, which is right because those pieces contain no mark. A step for gap g reads only entries with smaller gaps, so it writes a right value, and when the loop ends, best[0][m + 1] is the answer. The lesson on dry runs and invariants argues loops in the same three steps.

Rebuild the plan

The number alone rarely satisfies an interviewer, who asks next for the order of cuts. The table of first cuts holds it: cut the whole log at first[0][m + 1], then plan the left part and the right part the same way. Listing a piece’s first cut before the cuts of its parts always gives an order the saw can follow, because a piece exists before anything inside it is cut. For the log of 20 that is 12, then 6, then 9. The order between independent parts is free: any interleaving of the left plan and the right plan costs the same.

The code in five languages

The final version is the table without the plan. The Python and JavaScript tabs run here in the page; Java, C++ and Go appear in a recorded terminal session underneath, compiled with the versions this track pins.

def min_cut_cost(length, cuts):
    """The least total cost of making every cut, where a cut costs the length of the piece it falls on."""
    marks = [0, *sorted(cuts), length]  # sentinels at both ends
    n = len(marks)
    best = [[0] * n for _ in range(n)]  # best[i][j] = 0 when no mark lies between i and j
    for gap in range(2, n):  # by increasing length: every shorter piece is finished first
        for i in range(n - gap):
            j = i + gap
            best[i][j] = marks[j] - marks[i] + min(best[i][k] + best[k][j] for k in range(i + 1, j))
    return best[0][n - 1]


hundred = [i * 104_729 % 1_000_000 for i in range(1, 101)]  # 100 distinct marks on a log of 1,000,000
print(min_cut_cost(20, [6, 9, 12]))
print(min_cut_cost(10, [2, 4, 7]))
print(min_cut_cost(7, []))
print(min_cut_cost(7, [3]))
print(min_cut_cost(1_000_000, hundred))

38
20
0
7
6699201

function minCutCost(length, cuts) {
  const marks = [0, ...[...cuts].sort((a, b) => a - b), length]; // sentinels at both ends
  const n = marks.length;
  const best = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let gap = 2; gap < n; gap++) {
    for (let i = 0; i + gap < n; i++) {
      const j = i + gap;
      let cheapest = Infinity;
      for (let k = i + 1; k < j; k++) cheapest = Math.min(cheapest, best[i][k] + best[k][j]);
      best[i][j] = marks[j] - marks[i] + cheapest;
    }
  }
  return best[0][n - 1];
}

const hundred = Array.from({ length: 100 }, (_, i) => ((i + 1) * 104_729) % 1_000_000);
console.log(minCutCost(20, [6, 9, 12]));
console.log(minCutCost(10, [2, 4, 7]));
console.log(minCutCost(7, []));
console.log(minCutCost(7, [3]));
console.log(minCutCost(1_000_000, hundred));

38
20
0
7
6699201

import java.util.Arrays;

public class MinCut {
    static int minCutCost(int length, int[] cuts) {
        int[] marks = new int[cuts.length + 2]; // sentinels at both ends
        int[] sorted = cuts.clone();
        Arrays.sort(sorted);
        System.arraycopy(sorted, 0, marks, 1, sorted.length);
        marks[marks.length - 1] = length;
        int n = marks.length;
        int[][] best = new int[n][n];
        for (int gap = 2; gap < n; gap++) {
            for (int i = 0; i + gap < n; i++) {
                int j = i + gap;
                int cheapest = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) cheapest = Math.min(cheapest, best[i][k] + best[k][j]);
                best[i][j] = marks[j] - marks[i] + cheapest; // at most 100 cuts of 10^6 each: fits an int
            }
        }
        return best[0][n - 1];
    }

    public static void main(String[] args) {
        int[] hundred = new int[100];
        for (int i = 1; i <= 100; i++) hundred[i - 1] = i * 104_729 % 1_000_000;
        System.out.println(minCutCost(20, new int[] {6, 9, 12}));
        System.out.println(minCutCost(10, new int[] {2, 4, 7}));
        System.out.println(minCutCost(7, new int[] {}));
        System.out.println(minCutCost(7, new int[] {3}));
        System.out.println(minCutCost(1_000_000, hundred));
    }
}

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int min_cut_cost(int length, std::vector<int> cuts) {
    std::sort(cuts.begin(), cuts.end());
    std::vector<int> marks{0};  // sentinels at both ends
    marks.insert(marks.end(), cuts.begin(), cuts.end());
    marks.push_back(length);
    const int n = static_cast<int>(marks.size());
    std::vector<std::vector<int>> best(n, std::vector<int>(n, 0));
    for (int gap = 2; gap < n; ++gap) {
        for (int i = 0; i + gap < n; ++i) {
            const int j = i + gap;
            int cheapest = INT_MAX;
            for (int k = i + 1; k < j; ++k) cheapest = std::min(cheapest, best[i][k] + best[k][j]);
            best[i][j] = marks[j] - marks[i] + cheapest;  // at most 100 cuts of 10^6 each: fits an int
        }
    }
    return best[0][n - 1];
}

int main() {
    std::vector<int> hundred;
    for (int i = 1; i <= 100; ++i) hundred.push_back(i * 104'729 % 1'000'000);
    std::cout << min_cut_cost(20, {6, 9, 12}) << '\n';
    std::cout << min_cut_cost(10, {2, 4, 7}) << '\n';
    std::cout << min_cut_cost(7, {}) << '\n';
    std::cout << min_cut_cost(7, {3}) << '\n';
    std::cout << min_cut_cost(1'000'000, hundred) << '\n';
}

package main

import (
	"fmt"
	"math"
	"slices"
)

func minCutCost(length int, cuts []int) int {
	sorted := slices.Clone(cuts)
	slices.Sort(sorted)
	marks := append(append([]int{0}, sorted...), length) // sentinels at both ends
	n := len(marks)
	best := make([][]int, n)
	for i := range best {
		best[i] = make([]int, n)
	}
	for gap := 2; gap < n; gap++ {
		for i := 0; i+gap < n; i++ {
			j := i + gap
			cheapest := math.MaxInt
			for k := i + 1; k < j; k++ {
				cheapest = min(cheapest, best[i][k]+best[k][j])
			}
			best[i][j] = marks[j] - marks[i] + cheapest
		}
	}
	return best[0][n-1]
}

func main() {
	hundred := make([]int, 0, 100)
	for i := 1; i <= 100; i++ {
		hundred = append(hundred, i*104_729%1_000_000)
	}
	fmt.Println(minCutCost(20, []int{6, 9, 12}))
	fmt.Println(minCutCost(10, []int{2, 4, 7}))
	fmt.Println(minCutCost(7, []int{}))
	fmt.Println(minCutCost(7, []int{3}))
	fmt.Println(minCutCost(1_000_000, hundred))
}

from session import run, versions

# MinCut.java runs as a single source file, min_cut.cpp is built with the sanitizers on, and go run builds min_cut.go.
versions("java -version", "clang++ --version", "go version")
run("""
java MinCut.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined min_cut.cpp -o min_cut
./min_cut
go run min_cut.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java MinCut.java
38
20
0
7
6699201
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined min_cut.cpp -o min_cut
$ ./min_cut
38
20
0
7
6699201
$ go run min_cut.go
38
20
0
7
6699201

All five print the same five answers. The 100 marks are generated the same way in each language, as i × 104,729 modulo 1,000,000 for i from 1 to 100, which are distinct because 104,729 shares no factor with 1,000,000. The total cannot overflow anywhere: 100 cuts of at most 10⁶ credits each come to at most 10⁸, well inside the 2,147,483,647 of a Java int (Java Language Specification §4.2.1) and of the 32 or more bits of Go’s int. The java launcher compiles and runs MinCut.java in one go, as it has for single source files since Java 11 (JEP 330). The C++ binary was compiled with Clang’s address and undefined-behaviour sanitizers, and neither printed a report.

Check it against the brute force

"""The two interval DPs of the lesson against brute forces that try every order, on random inputs."""
import random
from functools import cache
from itertools import permutations


def min_cut_cost(length, cuts):  # the table of the lesson
    marks = [0, *sorted(cuts), length]
    n = len(marks)
    best = [[0] * n for _ in range(n)]
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            best[i][j] = marks[j] - marks[i] + min(best[i][k] + best[k][j] for k in range(i + 1, j))
    return best[0][n - 1]


def cuts_brute(length, cuts):  # every order of the cuts
    def cost(order):
        pieces, total = [(0, length)], 0
        for c in order:
            i = next(i for i, (a, b) in enumerate(pieces) if a < c < b)
            a, b = pieces[i]
            total += b - a
            pieces[i : i + 1] = [(a, c), (c, b)]
        return total

    return min(cost(order) for order in permutations(cuts))


def bind_cost(pages):  # the table of the lesson
    n = len(pages)
    prefix = [0]
    for p in pages:
        prefix.append(prefix[-1] + p)
    best = [[0] * n for _ in range(n)]
    for size in range(2, n + 1):
        for i in range(n - size + 1):
            j = i + size - 1
            best[i][j] = prefix[j + 1] - prefix[i] + min(best[i][k] + best[k + 1][j] for k in range(i, j))
    return best[0][n - 1]


@cache
def bind_brute(stacks):  # every choice of the next two neighbours to bind
    if len(stacks) == 1:
        return 0
    return min(
        stacks[i] + stacks[i + 1] + bind_brute(stacks[:i] + (stacks[i] + stacks[i + 1],) + stacks[i + 2 :])
        for i in range(len(stacks) - 1)
    )


rng = random.Random(2024)
logs = 0
for _ in range(1500):
    length = rng.randint(2, 40)
    cuts = rng.sample(range(1, length), rng.randint(0, min(6, length - 1)))
    assert min_cut_cost(length, cuts) == cuts_brute(length, cuts), (length, cuts)
    logs += 1
rows = 0
for _ in range(1500):
    pages = tuple(rng.randint(1, 60) for _ in range(rng.randint(1, 7)))
    assert bind_cost(list(pages)) == bind_brute(pages), pages
    rows += 1
print(f"{logs} random logs with up to 6 cuts: the table equals the best of every order")
print(f"{rows} random rows of up to 7 stacks: the table equals the best of every binding order")

1500 random logs with up to 6 cuts: the table equals the best of every order
1500 random rows of up to 7 stacks: the table equals the best of every binding order

The logs are short and the marks are dense on purpose, so that ties and adjacent marks occur often. The second half checks the problem of the next section in the same way. A check like this is cheap to write and catches a wrong range or a wrong loop order on the first few inputs; the stress-testing lesson builds the same harness for any problem.

Binding stacks of pages: the last merge

Here the useful operation to fix is the last one. Whatever happened before, the last binding of the stacks i to j joins a left part i to k and a right part k + 1 to j, each already bound into one, and it costs every page of i to j, whatever k is. Before that, the left part and the right part were bound independently. So

with bind(i, i) = 0, and a prefix-sum array gives each total in O(1), as in the prefix sums lesson. Notice the two differences from the log: the state is a range of stacks, both ends included, so k runs from i to j − 1; and the sentinels are not needed, because the row itself has ends.

from heapq import heapify, heappop, heappush


def bind_cost(pages):
    """The cheapest way to bind a row of stacks into one book, two neighbouring stacks at a time."""
    n = len(pages)
    prefix = [0]
    for p in pages:
        prefix.append(prefix[-1] + p)  # prefix[j + 1] - prefix[i] is the number of pages in stacks i to j
    best = [[0] * n for _ in range(n)]
    for size in range(2, n + 1):
        for i in range(n - size + 1):
            j = i + size - 1
            # The last binding joins stacks i..k and k+1..j, and costs every page of i..j, whatever k is.
            best[i][j] = prefix[j + 1] - prefix[i] + min(best[i][k] + best[k + 1][j] for k in range(i, j))
    return best[0][n - 1]


def cheapest_neighbours_first(pages):
    """A greedy guess: always bind the two neighbouring stacks with the fewest pages together."""
    stacks, total = list(pages), 0
    while len(stacks) > 1:
        i = min(range(len(stacks) - 1), key=lambda i: stacks[i] + stacks[i + 1])
        total += stacks[i] + stacks[i + 1]
        stacks[i : i + 2] = [stacks[i] + stacks[i + 1]]
    return total


def any_two_cheapest_first(pages):
    """If any two stacks could be bound, not only neighbours: Huffman's greedy, which is optimal for that version."""
    heap, total = list(pages), 0
    heapify(heap)
    while len(heap) > 1:
        joined = heappop(heap) + heappop(heap)
        total += joined
        heappush(heap, joined)
    return total


for pages in ([100, 90, 90, 100], [30, 100, 100, 30], [40, 10, 30, 20, 50]):
    print(pages)
    print("  interval DP:", bind_cost(pages))
    print("  cheapest neighbours first:", cheapest_neighbours_first(pages))
    print("  any two stacks, cheapest first:", any_two_cheapest_first(pages))

[100, 90, 90, 100]
  interval DP: 760
  cheapest neighbours first: 840
  any two stacks, cheapest first: 760
[30, 100, 100, 30]
  interval DP: 520
  cheapest neighbours first: 520
  any two stacks, cheapest first: 480
[40, 10, 30, 20, 50]
  interval DP: 340
  cheapest neighbours first: 350
  any two stacks, cheapest first: 330

The first row shows why the table is needed. Binding the cheapest neighbours first joins the two stacks of 90 into 180, which is then bound twice more, and pays 840; the table binds 100 with 90 and 90 with 100 and pays 760. The second row shows what the word “neighbouring” does. If any two stacks could be bound, the greedy rule “always join the two smallest” would be optimal, by Huffman’s theorem on minimum-redundancy codes; it binds the two stacks of 30 first and pays 480. Only neighbours may be joined here, so the two 30s cannot meet until everything between them has been bound, and the best is 520. Huffman’s algorithm and the merge order of this problem build the same kind of tree; the binding problem additionally keeps the leaves in their original order. That ordered version is known as the optimal alphabetic tree problem, and Hu and Tucker (1971), then Garsia and Wachs (1977), solved it in O(n log n). An interview expects the O(n³) table, and the bound in the last section brings it to O(n²).

The cost: n³, and what it means in seconds

The table tries every split of every piece, which is every triple i < k < j of the m + 2 marks: exactly (m + 2)(m + 1)m / 6 splits, 171,700 for 100 marks. The memory is the table, (m + 2)² entries. Read the count against the limits as the constraints lesson does, with a few simple steps per split: the cubic table suits a few hundred items in Python, as the run below shows, and around a thousand in C++, where 1,000 items mean about 1.7 × 10⁸ splits, a second or two.

Faster when the costs allow it: Knuth’s bound

For both problems of this lesson the best split moves in one direction as a piece grows: the best first cut of the piece i to j lies between the best first cuts of the two pieces one mark shorter, i to j − 1 and i + 1 to j. Knuth proved this for optimal binary search trees in 1971, and Yao later gave the general condition: the cost of a piece must satisfy a quadrangle inequality and must not shrink when the piece grows. The length of a piece and the total of a row of stacks satisfy both. Trying only the splits in that window costs O(n²) in all, because the windows of the pieces of one gap add up to O(n). The run below compares the two tables on the same random logs:

"""The cubic table against the same table with Knuth's bound on the split, counted and timed in CPython."""
import random
from time import perf_counter


def cubic(marks):
    n = len(marks)
    best = [[0] * n for _ in range(n)]
    checks = 0
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            checks += j - i - 1  # every mark strictly between i and j is tried
            best[i][j] = marks[j] - marks[i] + min(best[i][k] + best[k][j] for k in range(i + 1, j))
    return best[0][n - 1], checks


def knuth_bound(marks):
    """Only marks between the first cuts of the two pieces one mark shorter are tried: opt[i][j-1] <= k <= opt[i+1][j]."""
    n = len(marks)
    best = [[0] * n for _ in range(n)]
    opt = [[0] * n for _ in range(n)]
    checks = 0
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            lo, hi = (i + 1, j - 1) if gap == 2 else (opt[i][j - 1], opt[i + 1][j])
            k = min(range(lo, hi + 1), key=lambda k: best[i][k] + best[k][j])
            checks += hi - lo + 1
            best[i][j] = marks[j] - marks[i] + best[i][k] + best[k][j]
            opt[i][j] = k
    return best[0][n - 1], checks


rng = random.Random(7)
for m in (100, 200, 400):
    marks = [0, *sorted(rng.sample(range(1, 1_000_000), m)), 1_000_000]
    start = perf_counter()
    a, checks_a = cubic(marks)
    middle = perf_counter()
    b, checks_b = knuth_bound(marks)
    end = perf_counter()
    assert a == b
    print(f"{m} cuts, cost {a:,}")
    print(f"  cubic:       {checks_a:>10,} splits tried {1000 * (middle - start):8.1f} ms")
    print(f"  Knuth bound: {checks_b:>10,} splits tried {1000 * (end - middle):8.1f} ms")

100 cuts, cost 6,162,866
  cubic:          171,700 splits tried     84.3 ms
  Knuth bound:     10,386 splits tried      6.0 ms
200 cuts, cost 7,219,883
  cubic:        1,353,400 splits tried   1712.2 ms
  Knuth bound:     40,409 splits tried    130.0 ms
400 cuts, cost 8,159,910
  cubic:       10,746,800 splits tried  11250.6 ms
  Knuth bound:    157,456 splits tried    183.8 ms

The counts are exact and the same on every computer; the times are not. Doubling the marks multiplies the cubic count by about 8 and the bounded count by about 4, so at 400 marks the cubic table tries 68 times as many splits as the bounded one. Use the bound only when you can say why it holds for your cost, and keep the cubic table as the check it must agree with.

Recognising the pattern

The same three decisions solve a family of problems: what a piece is, which operation inside it to fix, and what that operation costs.

• Cutting a log at marks. The state is the piece between marks i and j; the choice is the first cut, at mark k; it costs the length of the piece.
• Binding neighbouring stacks. The state is stacks i to j; the choice is the last binding, between k and k + 1; it costs every page of stacks i to j.
• Multiplying a chain of matrices. The state is matrices i to j; the choice is the last product, between k and k + 1; it costs rows(i) × columns(k) × columns(j) scalar multiplications.
• Removing items whose neighbours then touch. The state is the items strictly between i and j; the choice is the item k removed last; its value depends on i, k and j, which are neighbours when k goes.
• An optimal binary search tree. The state is keys i to j; the choice is the root k; it adds the search frequencies of keys i to j, because every key of the piece sits one level deeper.

Two of these have results of their own: Hu and Shing found an O(n log n) algorithm for the matrix chain, published in two parts from 1982, and the binary search tree is the problem of Knuth’s paper. In an interview, the table and its O(n³) cost are the expected answer for all of them. The fourth problem deserves a second look, because fixing the first removal fails there: after it, the two sides become neighbours and are no longer independent. Fixing the last removal works, because the item removed last still has i and j as its neighbours, whatever happened inside.

Edge cases and common bugs

"""Four plausible mistakes against the right table, on every small log, smallest first."""
from itertools import combinations


def right(length, cuts):
    marks = [0, *sorted(cuts), length]
    n = len(marks)
    best = [[0] * n for _ in range(n)]
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            best[i][j] = marks[j] - marks[i] + min(best[i][k] + best[k][j] for k in range(i + 1, j))
    return best[0][n - 1]


def row_by_row(length, cuts):
    """Fills best[i][j] for i = 0, 1, 2 … and j upwards: best[k][j] for k > i is still 0 when it is read."""
    marks = [0, *sorted(cuts), length]
    n = len(marks)
    best = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 2, n):
            best[i][j] = marks[j] - marks[i] + min(best[i][k] + best[k][j] for k in range(i + 1, j))
    return best[0][n - 1]


def no_sentinels(length, cuts):
    """Uses only the cut marks as piece ends, so the pieces that reach the ends of the log are never priced."""
    marks = sorted(cuts)
    n = len(marks)
    if n < 3:
        return 0
    best = [[0] * n for _ in range(n)]
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            best[i][j] = marks[j] - marks[i] + min(best[i][k] + best[k][j] for k in range(i + 1, j))
    return best[0][n - 1]


def ends_included(length, cuts):
    """Lets the split k be i or j itself, so a piece can 'cut' at its own end for free."""
    marks = [0, *sorted(cuts), length]
    n = len(marks)
    best = [[0] * n for _ in range(n)]
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            best[i][j] = marks[j] - marks[i] + min(best[i][k] + best[k][j] for k in range(i, j + 1))
    return best[0][n - 1]


def unsorted_marks(length, cuts):
    """Keeps the marks in the order they were given."""
    marks = [0, *cuts, length]
    n = len(marks)
    best = [[0] * n for _ in range(n)]
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            best[i][j] = marks[j] - marks[i] + min(best[i][k] + best[k][j] for k in range(i + 1, j))
    return best[0][n - 1]


def small_logs():
    """Every log of length 2 to 9 with its marks, fewer cuts first, then smaller marks; each in two orders."""
    for length in range(2, 10):
        for m in range(length):
            for cuts in combinations(range(1, length), m):
                yield length, list(cuts)
                yield length, list(reversed(cuts))


for bug in (row_by_row, no_sentinels, ends_included, unsorted_marks):
    for length, cuts in small_logs():
        if bug(length, cuts) != right(length, cuts):
            print(f"{bug.__name__}: length {length}, cuts {cuts} gives {bug(length, cuts)}, the right answer is {right(length, cuts)}")
            break
    else:
        print(f"{bug.__name__}: no small log shows it")

row_by_row: length 3, cuts [1, 2] gives 3, the right answer is 5
no_sentinels: length 2, cuts [1] gives 0, the right answer is 2
ends_included: length 3, cuts [1, 2] gives 3, the right answer is 5
unsorted_marks: length 3, cuts [2, 1] gives 4, the right answer is 5

• Filling row by row reads entries of later rows that are still 0: a log of 3 cut at 1 and 2 comes out at 3 instead of 5. Loop over the gap first, or over i downwards.
• Forgetting the sentinels leaves the pieces that reach the ends of the log unpriced: one cut on a log of 2 costs nothing.
• Letting k be i or j lets a piece “cut” at its own end for free, so it reads the entry it is computing.
• Unsorted marks make some pieces negative: the marks must be sorted before the sentinels are added.
• Indexing by position instead of by mark. A table over positions 0 to 10⁶ has 10¹² cells; the 102 marks have 10,404. The state is always the smallest description of a piece.
• Overflow in the binding problem. 300 stacks of 10⁴ pages make 3 × 10⁶ pages, and a stack is bound at most n − 1 times, so the total stays below 9 × 10⁸: inside 32 bits, but not by much. Double both limits and Java, C++ and Go need 64-bit totals.

Exercise

min_cut_cost(7, [])           # 0: nothing to cut
min_cut_cost(7, [3])          # 4: the pieces are 3 and 4 long
min_cut_cost(20, [6, 9, 12])  # 21
min_cut_cost(10, [2, 4, 7])   # 11

def min_cut_cost(length, cuts):
    """The least total cost of every cut, when a cut costs the length of the longer piece it leaves."""
    # Replace this line with your code.
    return 0

import random
from itertools import permutations

from cuts import min_cut_cost


def every_order(length, cuts):
    """The answer the tests trust for a few cuts: every order of the cuts, priced one cut at a time."""

    def cost(order):
        pieces, total = [(0, length)], 0
        for c in order:
            i = next(i for i, (a, b) in enumerate(pieces) if a < c < b)
            a, b = pieces[i]
            total += max(c - a, b - c)
            pieces[i : i + 1] = [(a, c), (c, b)]
        return total

    return min(cost(order) for order in permutations(cuts))


def test_the_examples():
    """the four examples of the prompt"""
    assert min_cut_cost(7, []) == 0
    assert min_cut_cost(7, [3]) == 4
    assert min_cut_cost(20, [6, 9, 12]) == 21
    assert min_cut_cost(10, [2, 4, 7]) == 11


def test_no_cuts_and_one_cut():
    """no marks cost nothing; one mark costs its longer piece, wherever it is"""
    assert min_cut_cost(2, []) == 0
    assert min_cut_cost(1_000_000, []) == 0
    assert min_cut_cost(2, [1]) == 1
    assert min_cut_cost(1_000_000, [1]) == 999_999
    assert min_cut_cost(1_000_000, [500_000]) == 500_000


def test_marks_in_any_order():
    """the marks may arrive unsorted"""
    assert min_cut_cost(20, [12, 6, 9]) == 21
    assert min_cut_cost(10, [7, 2, 4]) == 11


def test_small_logs_against_every_order():
    """200 random logs with up to 6 cuts, against the best of every order"""
    rng = random.Random(41)
    for _ in range(200):
        length = rng.randint(2, 30)
        cuts = rng.sample(range(1, length), rng.randint(0, min(6, length - 1)))
        assert min_cut_cost(length, cuts) == every_order(length, cuts), f"min_cut_cost({length}, {cuts})"


def test_a_hundred_cuts():
    """100 marks on a log of 1,000,000: an O(m^3) table answers at once, a search over orders never would"""
    hundred = [i * 104_729 % 1_000_000 for i in range(1, 101)]
    assert min_cut_cost(1_000_000, hundred) == 3_588_642

/** The least total cost of every cut, when a cut costs the length of the longer piece it leaves. */
export function minCutCost(length, cuts) {
  // Replace this line with your code.
  return 0;
}

import { test, assert } from 'mysmartcopilot:test';
import { minCutCost } from './cuts.mjs';

/** The answer the tests trust for a few cuts: every order of the cuts, priced one cut at a time. */
function everyOrder(length, cuts) {
  let best = Infinity;
  const used = new Array(cuts.length).fill(false);
  const pieces = [[0, length]];
  function search(total, done) {
    if (done === cuts.length) {
      best = Math.min(best, total);
      return;
    }
    for (let m = 0; m < cuts.length; m++) {
      if (used[m]) continue;
      const c = cuts[m];
      const i = pieces.findIndex(([a, b]) => a < c && c < b);
      const [a, b] = pieces[i];
      used[m] = true;
      pieces.splice(i, 1, [a, c], [c, b]);
      search(total + Math.max(c - a, b - c), done + 1);
      pieces.splice(i, 2, [a, b]);
      used[m] = false;
    }
  }
  search(0, 0);
  return best;
}

/** A small seeded generator (Park and Miller's minimal standard), so every run tests the same logs. */
function generator(seed) {
  let s = seed;
  return (n) => {
    s = (s * 48_271) % 2_147_483_647; // the product stays below 2 ** 53, so it is exact
    return s % n;
  };
}

test('the four examples of the prompt', () => {
  assert.equal(minCutCost(7, []), 0);
  assert.equal(minCutCost(7, [3]), 4);
  assert.equal(minCutCost(20, [6, 9, 12]), 21);
  assert.equal(minCutCost(10, [2, 4, 7]), 11);
});

test('no marks cost nothing; one mark costs its longer piece, wherever it is', () => {
  assert.equal(minCutCost(2, []), 0);
  assert.equal(minCutCost(1_000_000, []), 0);
  assert.equal(minCutCost(2, [1]), 1);
  assert.equal(minCutCost(1_000_000, [1]), 999_999);
  assert.equal(minCutCost(1_000_000, [500_000]), 500_000);
});

test('the marks may arrive unsorted', () => {
  assert.equal(minCutCost(20, [12, 6, 9]), 21);
  assert.equal(minCutCost(10, [7, 2, 4]), 11);
});

test('120 random logs with up to 5 cuts, against the best of every order', () => {
  const next = generator(41);
  for (let t = 0; t < 120; t++) {
    const length = 2 + next(29);
    const marks = [];
    const wanted = Math.min(next(6), length - 1);
    while (marks.length < wanted) {
      const c = 1 + next(length - 1);
      if (!marks.includes(c)) marks.push(c);
    }
    assert.equal(minCutCost(length, marks), everyOrder(length, marks), `minCutCost(${length}, [${marks}])`);
  }
});

test('100 marks on a log of 1,000,000: an O(m^3) table answers at once, a search over orders never would', () => {
  const hundred = Array.from({ length: 100 }, (_, i) => ((i + 1) * 104_729) % 1_000_000);
  assert.equal(minCutCost(1_000_000, hundred), 3_588_642);
});

Interview questions

Fresher · What signals in a problem statement point to interval dynamic programming?

Three signals together. The input is a row, such as a sequence, a string or a chain, and every operation acts on a contiguous piece of it: cutting a piece, joining two neighbours, removing an item so that its neighbours touch. The cost of an operation depends on the piece, such as its length, its total or its end values, so the order of the operations changes the answer and a greedy rule is suspect. And the limits are small, with n in the hundreds, because the usual solution tries every split of every piece: about n²/2 pieces with up to n splits each, O(n³). If the pieces need not stay contiguous, as when any two stacks may be joined, the problem is a different one, often a greedy such as Huffman’s.

Fresher · Why is an interval DP table filled by increasing length rather than row by row?

Because each entry reads entries for shorter pieces inside it. To fill dp[i][j] you need dp[i][k] and dp[k][j] for every k strictly between i and j, and both are shorter than the piece from i to j. Looping over the length first, then over i, makes every shorter piece final before any longer one is computed. A row-by-row loop, with i from 0 upwards and j from i + 2 upwards, reads dp[k][j] for k greater than i, a row that has not been filled yet, so it sees zeros; on a log of length 3 cut at 1 and 2 it returns 3 instead of 5. Looping over i downwards from the end, with j upwards, also works, and a memoised recursion avoids choosing an order at all.

Key takeaways

• An interval DP has a state (i, j) for every contiguous piece and fixes one operation inside it, the first cut or the last merge, so that the two sides become independent.
• Fill the table by increasing length, or memoise; a row-by-row loop reads unfinished entries.
• Sentinels at both ends turn the edges of the input into ordinary marks.
• The cost is the number of pieces times the splits per piece: (m + 2)(m + 1)m / 6 splits for m marks, 171,700 for 100 marks and 10,746,800 for 400.
• Record the chosen split of every piece to rebuild the plan, listing a piece’s operation before those of its parts.
• Greedy rules fail here: cutting at the middle paid 40 instead of 38, and binding the cheapest neighbours paid 840 instead of 760. Huffman’s greedy works only when any two stacks may be joined.
• When the cost satisfies Knuth’s condition, the best split lies between the best splits of the two shorter pieces, and the table falls to O(n²): 157,456 splits instead of 10,746,800 at 400 marks.