Interval DP

Some problems work on a row of things that are joined or cut in some order: piles merged with their neighbours, matrices multiplied two at a time, a rail cut at marked places. The natural state is a stretch of the row, from position i to position j, and the table is filled from short stretches to long ones.

States that are stretches

An interval (or stretch) is a run of neighbouring positions i, i + 1, …, j of the row. Interval DP keeps one answer per stretch, best[i][j], in the upper half of a square table: row i, column j, with i ≤ j. A row of n things has n(n + 1)/2 stretches.

The rule always has the same shape. The last action on a stretch splits it in two at some place k, into i..k and k+1..j. Each side is a shorter stretch, solved separately, and the split itself has a cost. Try every k and keep the best:

The idea that makes this work: think about the last step, not the first. The first join of a pile row can happen anywhere and leaves a messy row behind. The last join always puts together two neighbouring blocks, each made only from its own piles.

Joining piles

A row of piles of stones is joined into one pile. Each step joins two neighbouring piles and costs the size of the new pile. The order matters: joining 4, 1, 3 as (4 + 1) then + 3 costs 5 + 8 = 13, while 4 + (1 + 3) costs 4 + 8 = 12. Whatever the order, the last join makes the whole stretch, so it costs the sum of piles i to j. Before that, the two blocks were built separately. So:

A single pile costs nothing: best[i][i] = 0. The second version of the figure fills the same table row by row, which breaks. Step through both.

from itertools import accumulate

def join_cost(a):
    n = len(a)
    pre = [0, *accumulate(a)]            # pre[j + 1] - pre[i] = a[i] + ... + a[j]
    best = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):       # shorter stretches first
        for i in range(n - length + 1):
            j = i + length - 1
            best[i][j] = pre[j + 1] - pre[i] + min(
                best[i][k] + best[k + 1][j] for k in range(i, j))
    return best[0][n - 1] if n else 0

The sum of a stretch comes from prefix sums (ARRS-4) in O(1), so the cost of a stretch never adds a loop.

Why shorter stretches go first

best[i][j] reads best[i][k] and best[k + 1][j]. Both are strictly shorter than i..j, because k < j and k + 1 > i. So if every stretch of length L − 1 or less is finished before any stretch of length L, every value read is final. This is a proof by induction on the length (CORR-3): stretches of length 1 are right by the base case, and a stretch of length L reads only shorter, finished stretches.

The usual row-by-row order fails, as the figure shows: best[0][2] needs best[1][2], which sits in a later row. Two other orders work: the rows from the bottom up (i from n − 1 down to 0, j rising), and the columns from left to right (j rising, i from j down to 0). Both finish every cell to the left and below before the cell itself. Memoisation finds a right order by itself.

The same shape elsewhere

• Multiplying a chain of matrices. Multiplying a p × q matrix by a q × r one takes p · q · r multiplications. For A · B · C, the brackets change the work but not the result. With sizes d₀ × d₁, d₁ × d₂, …, the last multiplication of i..j joins i..k with k+1..j and costs dᵢ · dₖ₊₁ · dⱼ₊₁ (counting the matrices from 0). The same table, with a different cost.
• Cutting a rail. Cuts are made at marked places, and each cut costs the length of the piece being cut. The first cut of a piece splits it into two pieces cut separately, so here the useful step is the first, not the last. That is the practice problem: the stretches are between neighbouring marks.
• Palindromes. The longest palindrome hidden in a string as a subsequence: best[i][j] is 2 + best[i + 1][j − 1] when the end letters match, and otherwise the better of dropping one end. No split loop, so O(n²).
• Search trees with known lookups. Keys with known lookup counts: choose the root of each stretch of keys to make the total depth of lookups smallest (an optimal binary search tree). Knuth found it in 1971, together with the speed-up of lesson 6.
• Cutting a polygon into triangles, and many “remove items from a row in the best order” puzzles, where the useful question is which item goes last, because it splits the row into two independent sides.

Cost, and memoised recursion

About n²/2 cells, each trying up to n splits: O(n³) time (n · n · n) and O(n²) memory (n · n). The exact count is about n³/6 split checks. In Python that is fine for a few hundred positions: 150 positions make about 560,000 checks, well under a second; 1,000 would make about 170 million, far too slow. Lesson 6 shows when the split range can be narrowed to reach O(n²).

Memoised recursion is a natural way to write interval DP: solve(i, j) calls solve(i, k) and solve(k + 1, j). Its depth is at most the length of the row, because each call is on a shorter stretch. With functools.cache keep that under about 200 in the browser (DYNP-2). The practice problem has at most 150 marks, so memoised recursion is fine there.

Now try ADDP-P3, Cutting a rail.