## 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 **i**^{th} matrix has the dimensions **(arr[i-1] x arr[i])**.

^{th}

**Example:**

Input:N = 5 arr = {40, 20, 30, 10, 30}Output:26000Explaination: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]
```