Question:

How to do brackets in Matrix Chain Multiplication using Python3

Summary

Here, we are solving a matrix chain multiplication problem with the help of a recursive approach with memorization.

Consider taking two parameters:

Dimensions of matrices- p

Number of matrices- n

Solution

#User function Template for python3

class Solution:

def matrixChainOrder(self, p, n):

# code here

dp = {}

def fun(i,j):

if i == j:

s = '' + chr(64 + i)

return [0, s]

key = str(i) + "$" + str(j)

if dp.get(key) != None : return dp[key]

mini = 1e20

s = ""

for k in range(i,j):

left = fun(i,k)

right = fun(k+1,j)

curr_operations = left[0] + (p[i-1] * p[k] * p[j]) + right[0]

if curr_operations < mini:

mini = curr_operations

s = "(" + left[1] + right[1] + ")"

dp[key] = [mini, s]

return dp[key]

return fun(1,n-1)[1];

Explanation

The method initializes a dictionary dp to store already computed results for subproblems. This is used for memoization to avoid redundant calculations.
Inside the method, there is a nested function fun(i, j). It takes two indices i and j representing the range of matrices to consider.
Suppose i is equal to j this means there is only one matrix in the range, the function returns [0, chr(64 + i)]. This indicates that no multiplication is needed, and the matrix is represented by a letter.
If the result for the subproblem with indices i to j is already computed and stored in the dp dictionary, it is directly returned.