Matrix Chain Multiplication

Statement

You are given a chain of matrices to be multiplied. You have to find the least number of primitive multiplications needed to evaluate the result.

Note: Given two matrices $A$ and $B$ of dimensions $(n \times m)$ and $(m \times l)$, the resulting matrix we get is $AB$, whose dimensions are $(n \times l)$. Further, when multiplying these two matrices, the number of primitive multiplications is $(n \times m \times l)$.

Your algorithm will take dims as input, a list denoting the dimensions of the matrices to be multiplied. Since the columns of the first matrix and the rows of the second matrix are the same, we have not repeated this information in the list dims. So the dimensions of the first matrix would be $(dims[0] \times dims[1])$ and the second matrix would have dimensions of $(dims[1] \times dims[2])$. Similarly, the dimensions of the third matrix would be $(dims[2] \times dims[3])$, and so on.

In the illustration below, we see that changing the order in which we multiply the three matrices affects the number of primitive multiplications required to compute the final result:

Constraints:

• 3 $\leq$ dims.length $\leq$ 500
• 1 $\leq$ dims[i] $\leq$ $10^3$

Examples

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Recursive Numbers dynamic programming pattern.

Naive approach

We can easily imagine dims to be a list of matrices. Then each recursive call tries to find the optimal placement of two parentheses between these matrices. So, let’s say we have the following sequence of matrices: $A_1 A_2 A_3A_4$. Each recursive call tries to place two parentheses, so we have the following possibilities:

• $(A_1)(A_2A_3A_4)$ ...