Interval DP in Python: matrix chain multiplication

Why this lesson matters

Matrix multiplication is used in graphics, machine learning and scientific code. Multiplying a long chain of matrices takes a lot of arithmetic, and the order you multiply them in can change that amount by a large factor. A chain of three matrices can cost 4,500 multiplications in one order and 27,000 in another, even though the final result is the same.

Matrix chain multiplication is the classic problem that asks for the cheapest order. It is also the classic example of interval dynamic programming. An interval is a range of neighbouring items, here a range of matrices from number i to number j. The program solves every interval once, shortest first, and stores the answers in a table. The answer for the whole chain is then read from the table.

By the end of this lesson you will be able to compute the cost of multiplying two matrices, explain why a split point is the decision that matters, fill the table in the right order, rebuild the best order as text, and avoid the common errors in the list sizes and fill order.

The earlier lessons in this module covered the one-dimensional and grid tables. Lesson 21 covered digit DP. This lesson uses a two-dimensional table, where the row and column are the two ends of a range.

Reading the code in this lesson

The code uses a few Python features. You need only these to follow it.

• A list of lists, such as best = [[0] * n for _ in range(n)], is a table. best[i][j] reads or writes the cell in row i and column j. Both indexes start at 0.
• range(a, b) gives the numbers from a up to b, but not b. So range(i, j) gives i, i + 1, up to j - 1.
• math.inf is a value that is larger than any number. It is used as a starting value for a minimum. The first split always beats it, so after that the stored cost is an ordinary integer again.
• A function can return two values at once, such as return best[0][n - 1], split. The caller unpacks them with cost, split = min_cost(dims).
• An f-string such as f"A{i + 1}" puts the value of an expression inside braces in the text.
• The last lines of the program are if __name__ == "__main__": and a call to main(). Python runs main only when you start the file directly.

Multiplying two matrices and what it costs

A matrix is a grid of numbers with rows and columns. A matrix with 10 rows and 30 columns is written 10 by 30. Two matrices can be multiplied only when the number of columns of the first equals the number of rows of the second.

Take A, which is 10 by 30, and B, which is 30 by 5. The product has the rows of A and the columns of B, so it is 10 by 5. To fill each of its 50 cells, you take one row of A and one column of B and multiply the 30 pairs of numbers, then add the 30 products together. That is 30 multiplications per cell.

The total number of multiplications is 10 times 5 times 30, which is 1500. The general rule is this. Multiplying a p by q matrix with a q by r matrix costs p times q times r multiplications, and the result is p by r.

The cost of a multiplication is the number of multiplications, not the time it takes. That is the usual measure in this problem, and the lesson uses it throughout.

Why the order changes the cost

Now take three matrices in a chain: A is 10 by 30, B is 30 by 5, and C is 5 by 60. Matrix multiplication is associative (the grouping does not change the result), so (A times B) times C and A times (B times C) give the same final 10 by 60 result. The cost is different.

Order one: multiply A and B first, then the result by C.

• A times B costs 10 times 30 times 5, which is 1500. The result is 10 by 5.
• That result times C costs 10 times 5 times 60, which is 3000. The result is 10 by 60.
• Total: 1500 + 3000 = 4500.

Order two: multiply B and C first, then A by the result.

• B times C costs 30 times 5 times 60, which is 9000. The result is 30 by 60.
• A times that result costs 10 times 30 times 60, which is 18000.
• Total: 9000 + 18000 = 27000.

The second order costs six times as much. The task is to find the cheapest order for a chain of any length.

Storing the sizes

The sizes of the chain are stored in one list of numbers called dims. For n matrices there are n + 1 numbers. The first two numbers give the size of matrix 1, the second and third give the size of matrix 2, and so on. In general, matrix i has size dims[i] by dims[i + 1].

For the three matrices above, the list is 10, 30, 5, 60. Matrix A is dims[0] by dims[1], which is 10 by 30. Matrix B is 30 by 5, and matrix C is 5 by 60. The list has four numbers because three matrices need four boundaries.

The code uses 0-based numbers, so the first matrix is number 0. When the text says A1, A2 and A3, it means the matrices with code numbers 0, 1 and 2.

The idea: pick a split point for each range

Take a range of matrices from i to j, inclusive. To multiply the whole range, you must split it into a left part and a right part. The split point k is the last matrix of the left part. The left part is the range from i to k, and the right part is the range from k + 1 to j. Each part is multiplied on its own, and then the two results are multiplied together.

The cost of a split is three things added together.

1. The cheapest cost of the left part, which is a smaller range.
2. The cheapest cost of the right part, which is also a smaller range.
3. The cost of multiplying the two results. The left result is dims[i] by dims[k + 1], and the right result is dims[k + 1] by dims[j + 1]. Their product costs dims[i] times dims[k + 1] times dims[j + 1].

Write best[i][j] for the cheapest cost of the range from i to j. Then the rule is:

best[i][i] = 0
best[i][j] = the minimum over k from i to j - 1 of
             best[i][k] + best[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]

A range of one matrix needs no multiplication, so its cost is 0. A range of two or more matrices tries every split point and keeps the cheapest.

The answer for the whole chain is best[0][n - 1].

Why the table is filled by length

The rule for best[i][j] uses best[i][k] and best[k + 1][j], which are ranges shorter than the range from i to j. So the shorter ranges must be filled first. The simplest safe order is by length. First fill every range of two matrices, then every range of three, and so on, until the full chain of n matrices is filled.

Length is the number of matrices in the range. A range from i to j has length j - i + 1.

Worked example 1: three matrices by hand

Use the sizes 10, 30, 5, 60. There are three matrices, so there are three ranges of length two or more.

Start with the ranges of length 2. Each one has only one split point.

• Range A1 to A2, which is code range 0 to 1. The only split is k = 0. The cost is 0 + 0 + 10 times 30 times 5, which is 1500.
• Range A2 to A3, which is code range 1 to 2. The only split is k = 1. The cost is 0 + 0 + 30 times 5 times 60, which is 9000.

Next is the range of length 3, which is the whole chain, code range 0 to 2. It has two split points.

• Split k = 0, so the left part is A1 and the right part is A2 times A3. The cost is best of A1 (0) plus best of A2 to A3 (9000) plus 10 times 30 times 60 (18000). The total is 27000.
• Split k = 1, so the left part is A1 times A2 and the right part is A3. The cost is best of A1 to A2 (1500) plus best of A3 (0) plus 10 times 5 times 60 (3000). The total is 4500.

The smaller total is 4500, from split k = 1. The table after the three steps is this.

The order that gives 4500 is (A1 times A2) times A3, which matches the earlier calculation.

Worked example 2: a chain of five matrices

Here is a chain of five matrices with sizes 4, 10, 3, 12, 20, 7. That is six numbers, so there are five matrices. Take the matrices as A1 (4 by 10), A2 (10 by 3), A3 (3 by 12), A4 (12 by 20) and A5 (20 by 7).

The shortest ranges cost the following.

• A1 times A2: 4 times 10 times 3 = 120.
• A2 times A3: 10 times 3 times 12 = 360.
• A3 times A4: 3 times 12 times 20 = 720.
• A4 times A5: 12 times 20 times 7 = 1680.

Now the ranges of three matrices. Take A1 to A3 as the example. It has two splits.

• Split after A1: A1 alone, then A2 times A3 (cost 360). The product of A1 (4 by 10) with the result of A2 times A3 (10 by 12) costs 4 times 10 times 12 = 480. Total 0 + 360 + 480 = 840.
• Split after A2: A1 times A2 (cost 120), then A3 alone. The product of the result (4 by 3) with A3 (3 by 12) costs 4 times 3 times 12 = 144. Total 120 + 0 + 144 = 264.

The cheaper split is after A2, with cost 264. Each range of length 3 and 4 is filled the same way, and the full chain has four possible split points at the top level. Working all of them by hand takes a long time, which is why the program does the table fill.

The point of the example is the pattern: every cell of the table tries each split once, and the cell reads only from shorter ranges that have already been filled.

The code

The complete program is below. It has the table fill, the rebuild of the order, a plain recursion for checking, and the example inputs. The first part of the file contains the two functions that matter, min_cost and parenthesise.

Save it as matrix_chain.py and run it with python3 matrix_chain.py. The output on Python 3.14.4 is:

small cost = 4500
small order = ((A1 A2) A3)
clrs cost = 15125
clrs order = ((A1 (A2 A3)) ((A4 A5) A6))
mismatches against the plain recursion: 0
100 matrices of 10000 by 10000 cost = 99000000000000

The random chains use Python's random module with the seed 42. Python's generator gives different numbers from the generator in Java, so these 500 chains are not the same chains as in a Java run of this program. The check is the same, though: the table answer must equal the plain recursion for every chain.

Reading the table loops

The outer loop length goes from 2 to n. This is the fill by length. Inside it, i runs over every start of a range of length length. The range range(n - length + 1) gives the starts that leave room for the whole range inside the chain. Then j = i + length - 1 is the end of that range.

The loop over k tries each split. The cost of a split uses best[i][k] and best[k + 1][j]. Both were filled in an earlier pass of length, because they are shorter.

When a split gives a lower cost, the code stores its position in split[i][j]. The table best is used only during the fill. The answer is read from its top-right corner, best[0][n - 1].

The function parenthesise rebuilds the order from the stored splits. A single matrix is printed as its name, which is its code number plus 1. A longer range is split at split[i][j] and each half is rebuilt the same way. The recursion ends at single matrices.

The check

The function slow_cost uses the same recurrence but without a table. It recalculates the same ranges many times, so it is far too slow for long chains. It is used only on chains of at most seven matrices, to confirm that the table gives the same answer. The program ran 500 random chains and found 0 mismatches.

Common mistakes

Filling the table in the wrong order

The table must be filled so that shorter ranges come before longer ones. A common wrong attempt fills rows from the top, with i going up from 0 and j inside it. The function below does that, and it is wrong.

def wrong_fill(dims):
    n = len(dims) - 1
    best = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            cheapest = math.inf
            for k in range(i, j):
                cost = best[i][k] + best[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                cheapest = min(cheapest, cost)
            best[i][j] = cheapest
    return best[0][n - 1]

When i is 0 and j is 3, the split k = 1 reads best[2][3]. That row has not been filled yet, so the cell still holds 0. The program treats the cost of multiplying the right part as free. On the six matrices with sizes 30, 35, 15, 5, 10, 20, 25, the correct answer is 15125 and the wrong order prints a smaller number. Calling min_cost and wrong_fill on that list prints:

right order = 15125
wrong order = 9000

The fix is the fill by length, as in the main program. Another safe fix is to fill rows from the bottom, with i going down from n - 1 and j going up. In Python that is the loop header for i in range(n - 1, -1, -1):, with the same body as above. In that order, every row k + 1 is already done when it is read. A version with this fix gave 15125 on the six-matrix list and matched min_cost on 300 random chains.

Sizing the table wrongly

The table has one row and one column for each matrix, so for n matrices it must be n by n. In Python a list does not grow when you write past its end. A write to a list index that does not exist raises an error. The example below uses a table of 2 by 2 and writes to column 2.

split = [[0] * 2 for _ in range(2)]
split[0][2] = 1

Its output is:

IndexError: list assignment index out of range

The message says that the index of an assignment is outside the list. Row 0 has two slots, with indexes 0 and 1, so column 2 does not exist. The table must have n rows and n columns. The function min_cost builds its own table with [[0] * n for _ in range(n)], so this mistake happens only when you build a table by hand.

Confusing the number of matrices with the number of sizes

Three matrices need four numbers in dims, not three. A common error is to pass the number of matrices and to use len(dims) as if it were the matrix count. The program computes n = len(dims) - 1, so the count of matrices is one less than the length of dims.

Leaving out the cost of the final multiplication

The cost of a split is three parts, and the last part is the product of the two results. A recurrence that adds only best[i][k] + best[k + 1][j] gives a cost that is too small. It treats the final multiplication as free, so it prefers splits that look cheap but are not. Always add dims[i] * dims[k + 1] * dims[j + 1].

Expecting the costs to overflow

Python integers have no fixed size, so a cost can be as large as it needs to be. The result for 100 matrices of size 10,000 by 10,000 is 99 times 10^12, which is 99000000000000. Python stores that value exactly. Some libraries use fixed-size integer types, which wrap around when a value is too large. The digit DP lesson, lesson 21, shows the same check for counts.

Practice

Exercise 1

Find the cheapest cost and order for the chain with sizes 5, 10, 3, 12, 5, 50, 6. That is six matrices.

Show the answer

The cheapest cost is 2010, and the order is ((A1 A2) ((A3 A4) (A5 A6))). The function min_cost gives 2010 with this order. You can check the order by hand. A1 times A2 costs 5 times 10 times 3 = 150. A3 times A4 costs 3 times 12 times 5 = 180. A5 times A6 costs 5 times 50 times 6 = 1500. Then (A3 A4) times (A5 A6) is 3 by 5 times 5 by 6, which costs 3 times 5 times 6 = 90. Last, (A1 A2) times the 3 by 6 result costs 5 times 3 times 6 = 90. The total is 150 + 180 + 1500 + 90 + 90 = 2010.

Exercise 2

Find the cheapest cost for the chain with sizes 4, 10, 3, 12, 20, 7, which has five matrices. Then check the cost of the order ((A1 A2) ((A3 A4) A5)) by adding up each multiplication.

Show the answer

The cheapest cost is 1344, and the order is ((A1 A2) ((A3 A4) A5)). The steps are: A1 times A2 costs 4 times 10 times 3 = 120. A3 times A4 costs 3 times 12 times 20 = 720. The result of A3 times A4 (3 by 20) times A5 (20 by 7) costs 3 times 20 times 7 = 420. The result of A1 times A2 (4 by 3) times the result of the right part (3 by 7) costs 4 times 3 times 7 = 84. The total is 120 + 720 + 420 + 84 = 1344.

Exercise 3

Find the cheapest cost for the chain with sizes 1, 2, 3, 4, and state the order that gives it.

Show the answer

The cheapest cost is 18, and the order is ((A1 A2) A3). A1 times A2 costs 1 times 2 times 3 = 6, and the result (1 by 3) times A3 (3 by 4) costs 1 times 3 times 4 = 12. The total is 18. The other order costs 2 times 3 times 4 = 24 for A2 times A3, plus 1 times 2 times 4 = 8 for the final product, which is 32.

Exercise 4

A chain of four matrices can be fully bracketed in several ways. How many different orders are there for four matrices, and how is that count found for n matrices?

Show the answer

There are 5 orders for four matrices. The count for n matrices is the Catalan number C(n - 1), where the Catalan numbers are 1, 1, 2, 5, 14, 42 and so on. For four matrices the count is C(3) = 5, and for three matrices it is C(2) = 2, which matches the two orders in the first worked example. The number grows very fast, which is why trying every order by brute force stops being practical: 20 matrices already have about 1.8 billion orders.

Exercise 5

Explain why the value stored in split[i][j] is enough to print the best order, without storing the whole table of orders.

Show the answer

Each range is split into exactly two parts at one split point. The best order for the whole range is the best order for the left part, multiplied by the best order for the right part. So the stored split point tells you where the top-level multiplication happens. The function parenthesise then repeats the same step for the two parts. Only one number per range is needed, which is the position of the split.

Summary

• The cost of multiplying a p by q matrix with a q by r matrix is p times q times r.
• The order of a chain changes the total cost, even though the final result stays the same.
• For a range of matrices, choose one split point, add the costs of the two parts, and add the cost of the final multiplication.
• Fill the table in order of increasing range length, so each part is ready before it is used.
• Store the best split for each range, so the best order can be printed without a second search.
• Python integers have no fixed size, so the costs of large chains do not wrap around.