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

Solution Review: The Matrix Chain Multiplication

Explore multiple solutions for the matrix chain multiplication problem, including simple recursion and dynamic programming approaches. Learn how to optimize time and space complexity by applying top-down memoization and bottom-up techniques to efficiently solve this classic dynamic programming challenge.

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)
...