Interval DP

The Idea

Some problems are indexed by a stretch rather than a prefix. The answer for i..j depends on every way to cut it into two shorter stretches, so the table is filled by length: pairs first, then triples, and so on. Matrix chains, burst balloons and palindrome partitioning all wear this shape.

Real-World Example

A data pipeline multiplying three matrices of shapes 10×30, 30×5 and 5×60. Both orders give the same output, but one costs 4,500 multiplications and the other 27,000. The planner prices the cuts before running a single one.

The Code

dims = [10, 30, 5, 60]               # 10x30, 30x5, 5x60
n = len(dims) - 1
best = [[0] * n for _ in range(n)]

for length in range(2, n + 1):       # short stretches first
    for i in range(n - length + 1):
        j = i + length - 1
        best[i][j] = min(
            best[i][k] + best[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
            for k in range(i, j)     # every place to cut the stretch
        )

print(best[0][n - 1])   # 4500, against 27000 for the other order

# cost of multiplying a 5x10 by a 10x20 matrix,
# then that result by a 20x2 matrix
first = 5 * 10 * 20
second = 5 * 20 * 2
print(first + second)