Splitting a range at every point

Interval problems share a shape: the answer for a range is built from two smaller ranges, and you try every place to cut.

The template

def interval_dp(n, cost):
    table = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):              # shorter ranges first
        for i in range(n - length + 1):
            j = i + length - 1
            table[i][j] = min(
                table[i][k] + table[k + 1][j] + cost(i, k, j)
                for k in range(i, j)
            )
    return table[0][n - 1]

Three loops: the length, the start, the split point. O(n^3), which is why these problems come with small bounds.

The answer is at table[0][n-1], the range covering everything, which is the identifying sign of this family.

Matrix chain

Multiplying a p x q by a q x r costs p*q*r. The result is the same whatever order you choose; the cost is not.

dimensions 10x100, 100x5, 5x50

(A B) C  ->  10*100*5  + 10*5*50   =  5,000 +  2,500 =  7,500
A (B C)  ->  100*5*50  + 10*100*50 = 25,000 + 50,000 = 75,000

A factor of ten from bracketing alone. The cost function is dim[i] * dim[k+1] * dim[j+1], the single multiplication joining the halves.

Why greedy fails here

"Always multiply the cheapest adjacent pair" is a real heuristic that real people try. It fails because the cheap multiplication can leave an awkward dimension at the join, making both remaining sides expensive. The best split is not visible locally, which is the general condition for needing a table.

The fill order trap

The plain nested loop over i and j is wrong here, and it does not crash.

table[i][j] reads table[i][k] and table[k+1][j]. The second has a larger i, so in an increasing i loop it has not been computed. The table fills with numbers derived from zeroes.

Looping by length guarantees every shorter range is finished.

Others in the family

That last row is the variation worth knowing: fixing the last operation rather than the split point, because fixing the first leaves the halves entangled.