Search⌘ K
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Solution Review: The Matrix Chain Multiplication

In this lesson, we will solve the matrix chain multiplication problem with different techniques of dynamic programming.

We'll cover the following...

Solution 1: Simple recursion #

Python 3.5
import numpy as np
def minMultiplications(dims):
    if len(dims) <= 2:
        return 0
    minimum = np.inf
    for i in range(1,len(dims)-1):
        minimum = min(minimum, minMultiplications(dims[0:i+1]) + minMultiplications(dims[i:]) +
                    dims[0] * dims[-1] * dims[i])
    return minimum
print(minMultiplications([3, 3, 2, 1, 2]))

Explanation

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: A1A2A3A4A_1 A_2 A_3A_4. Each recursive call tries to place two parentheses, so we have the following possibilities:

  • (A1)(A2A3A4)(A_1)(A_2A_3A_4)
  • (A1A2)(A3A4)(A_1A_2)(A_3A_4)
  • (A1A2A3)(A4)
...