Matrix Chain Multiplication – Python Solution

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The efficient way is the one that involves the least number of multiplications.
The dimensions of the matrices are given in an array arr[] of size N (such that N = number of matrices + 1) where the ith matrix has the dimensions (arr[i-1] x arr[i]).
Example: 
Input: N = 5
arr = {40, 20, 30, 10, 30}
Output: 26000
Explaination: There are 4 matrices of dimension 
40x20, 20x30, 30x10, 10x30. Say the matrices are 
named as A, B, C, D. Out of all possible combinations,
the most efficient way is (A*(B*C))*D. 
The number of operations are -
20*30*10 + 40*20*10 + 40*10*30 = 26000.
Python Solution:
class Solution:
   def matrixMultiplication(self, N, arr):
   # code here
     dp = [[0 for x in range(N)] for y in range(N)]
     temp_cost = 0
     for diff in range(1,N-1):
       for i in range(1,N-diff):
          j = i + diff
          min_cost = float('inf')
          for k in range(i,j):
             temp_cost = dp[i][k] + dp[k+1][j] + arr[i-1]arr[k]arr[j]
             if(temp_cost < min_cost):
                min_cost = temp_cost
          dp[i][j] = min_cost
     return dp[1][N-1]

Leave a Comment

Your email address will not be published. Required fields are marked *