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]
