Matrix Chain Multiplication

Q: What is the time complexity of matrix chain multiplication?

The table has about n²/2 stretches and each tries up to n splits, so dynamic programming runs in O(n³) time with O(n²) memory. Plain recursion without a memo makes 3^(n-1) calls for n matrices.

Q: Why does the order of matrix multiplication matter?

Matrix multiplication is associative, so (AB)C and A(BC) give the same matrix, but the intermediate matrices differ in size. In the first example (AB)C builds a 4 × 3 matrix and costs 264, while A(BC) builds a 10 × 12 matrix and costs 840.

Q: How do you find the optimal parenthesization itself?

Store the winning split in choice[left][right] next to best[left][right] . To print, a single matrix prints its name; a longer stretch prints an opening parenthesis, the part up to choice[left][right] , the part after it, and a closing parenthesis. This adds O(n²) memory.

HardDynamic programming

+10

A chain of matrices is described by dims: matrix i has dims[i] rows and dims[i+1] columns, so each matrix fits the next one. Multiplying a p × q matrix by a q × r matrix takes p × q × r scalar multiplications and gives a p × r matrix. Every way of placing the parentheses gives the same final product, but not at the same cost. Return the fewest scalar multiplications needed to multiply the whole chain.

Function

matrixChainOrder(dims: integer-array) → integer

dimsinteger-array: the sizes along the chain: matrix i is dims[i] × dims[i+1]
Returnsinteger: the fewest scalar multiplications that multiply the whole chain

Constraints

2 ≤ dims.length ≤ 100, so the chain holds between 1 and 99 matrices.
1 ≤ dims[i] ≤ 100
The answer is at most 98 × 10⁶, well inside a 32-bit signed integer.

Examples

Input: dims = [4, 10, 3, 12]
Output: 264
Explanation: Multiplying the first two costs 4 × 10 × 3 = 120 and leaves a 4 × 3 matrix, which times the 3 × 12 matrix adds 144: 264. The other order costs 360 + 480 = 840.

Follow-up

Can you also count how many different parenthesizations reach the minimum cost?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The order changes the cost: 264 against 840 in the first example. Look at the last multiplication. It joins the products of a left part and a right part of the chain, and each part is the same problem on a shorter chain. A table over the stretches of the chain solves each one once, in O(n³) time.

Try every split with plain recursion

Correct, but does not finish on the largest tests

Intuition

Number the boundaries of the chain from 0 to m-1, where m = dims.length: boundary k has size dims[k]. The matrices between boundaries left and right multiply to a dims[left] × dims[right] matrix in any order. So if the last step splits that stretch at split, it costs dims[left] × dims[split] × dims[right], whatever happened inside the two blocks. Each block should be built as cheaply as possible, so cheapest(left, right) is the smallest sum of both blocks' costs plus that last step, over every split. Trying every last step makes it correct.

It solves the same stretches again and again: n matrices take 3^(n-1) calls, about 1.2 × 10^9 for 20 matrices, while there are only about m²/2 different stretches.

Algorithm

Write cheapest(left, right) for the matrices between boundaries left and right.
If right - left < 2, there is one matrix: return 0.
For every split strictly between them, add cheapest(left, split), cheapest(split, right) and dims[left] × dims[split] × dims[right].
Return the smallest sum.
The answer is cheapest(0, m-1).

def matrixChainOrder(dims):
    def cheapest(left, right):
        # The fewest multiplications for the matrices between boundaries left and right
        if right - left < 2:
            return 0  # a single matrix costs nothing
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        return best

    return cheapest(0, len(dims) - 1)

Recursion with a memo

Intuition

A call depends only on left and right. Save its result in memo[left][right], with every cell starting at -1, a value no real cost can take, and later calls read the cell instead of recursing. Each of the about m²/2 pairs is solved once with fewer than m splits: O(n³), or 161,700 split checks for 99 matrices. The recursion is never deeper than the chain is long, so 100 boundaries fit on any call stack.

Algorithm

Allocate memo with m rows and m columns, every cell -1.
In cheapest(left, right), a stretch of one matrix returns 0, and a cell other than -1 returns its saved cost.
Otherwise price every split exactly as the plain recursion does and take the minimum.
Write that minimum into memo[left][right] before returning it.
The answer is cheapest(0, m-1).

def matrixChainOrder(dims):
    m = len(dims)
    # memo[left][right]: the answer for boundaries left and right, -1 while unknown
    memo = [[-1] * m for _ in range(m)]

    def cheapest(left, right):
        if right - left < 2:
            return 0  # a single matrix costs nothing
        if memo[left][right] != -1:
            return memo[left][right]
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        memo[left][right] = best
        return best

    return cheapest(0, m - 1)

Fill the table by stretch width

Intuition

Each cell depends only on narrower stretches, so loops can fill best[left][right] from narrow to wide. Width 1 is a single matrix and stays 0; when you reach a wider stretch, both parts of every split are already done. With dims = [6, 2, 7, 3, 5]:

Width 2: best[0][2] = 84, best[1][3] = 42, best[2][4] = 105.
Width 3: best[0][3] is 78 (split 1: 0 + 42 + 36), best[1][4] is 72 (split 3: 42 + 0 + 30).
Width 4: splits 1, 2 and 3 give 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 and 78 + 0 + 90 = 168, so best[0][4] = 132.

The top split at boundary 1 means the 6 × 2 matrix joins last, as in the second example. Time and memory match the memo version, with no recursion.

Algorithm

Let m = dims.length and allocate an m × m table best of zeros.
Loop width from 2 to m-1. Inside it, loop left upward from 0 while right = left + width is still a boundary.
For that stretch, compute best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right] for every split from left+1 to right-1, and store the minimum in best[left][right].
The answer is in best[0][m-1].

def matrixChainOrder(dims):
    m = len(dims)
    # best[left][right]: the fewest multiplications for the matrices
    # between boundary left and boundary right (0 for a single matrix)
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            low = None
            for split in range(left + 1, right):
                # the last product joins a dims[left] x dims[split] block
                # with a dims[split] x dims[right] block
                cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
                if low is None or cost < low:
                    low = cost
            best[left][right] = low
    return best[0][m - 1]

Pitfalls and edge cases

Multiplying the cheapest pair first. On [10, 10, 1, 9] the last pair is cheapest (90), but the step after it costs 900, for 990. Taking the first pair first costs 190.
Reading the answer from the wrong cell. dims has one more entry than there are matrices, so the answer is best[0][m-1], not best[0][m].
Looping left upward in the outer loop. Row left then reads best[split][right] from a later row that is still 0. Put the width in the outer loop, or count left down.
Missing the single matrix. [3, 7] must return 0, and in R the loop 2:(m-1) becomes 2:1 and runs backwards, so guard it.

Frequently asked questions3

What is the time complexity of matrix chain multiplication?

The table has about n²/2 stretches and each tries up to n splits, so dynamic programming runs in O(n³) time with O(n²) memory. Plain recursion without a memo makes 3^(n-1) calls for n matrices.

Why does the order of matrix multiplication matter?

Matrix multiplication is associative, so (AB)C and A(BC) give the same matrix, but the intermediate matrices differ in size. In the first example (AB)C builds a 4 × 3 matrix and costs 264, while A(BC) builds a 10 × 12 matrix and costs 840.

How do you find the optimal parenthesization itself?

Store the winning split in choice[left][right] next to best[left][right]. To print, a single matrix prints its name; a longer stretch prints an opening parenthesis, the part up to choice[left][right], the part after it, and a closing parenthesis. This adds O(n²) memory.

def matrixChainOrder(dims):
    # Write code here

Test #1

Test #2

Test #3

Argument

dims = [4, 10, 3, 12]

Expected Output

Matrix Chain Multiplication

Function

Constraints

Examples

Hints

Solution

Try every split with plain recursion

Recursion with a memo

Fill the table by stretch width

Pitfalls and edge cases

Frequently asked questions3

Similar problems