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]).
Example 1:
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.
Example 2:
Input: N = 4
arr = {10, 30, 5, 60}
Output: 4500
Explaination: The matrices have dimensions 
10*30, 30*5, 5*60. Say the matrices are A, B 
and C. Out of all possible combinations,the
most efficient way is (A*B)*C. The 
number of multiplications are -
10*30*5 + 10*5*60 = 4500.
Your Task:
You do not need to take input or print anything. Your task is to complete the function matrixMultiplication() which takes the value N and the array arr[] as input parameters and returns the minimum number of multiplication operations needed to be performed.
Expected Time Complexity: O(N^{3})
Expected Auxiliary Space: O(N^{2})
Constraints: 
2 ≤ N ≤ 100
1 ≤ arr[i] ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    def matrixMultiplication(self, N, arr):
        # code here

Solutions:
class Solution:

	def matrixMultiplication(self, N, arr):
		maxint = 10 ** 9 + 7
		table = [[0 for _ in range(N)] for _ in range(N)]
		for i in range(N):
			table[i][i] = 0
		for L in range(2, N):
			for i in range(1, N - L + 1):
				j = i + L - 1
				table[i][j] = maxint
				for k in range(i, j):
					Q = table[i][k] + table[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					table[i][j] = min(Q, table[i][j])
		return table[1][N - 1]


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for _ in range(N)] for _ in range(N)]
		for i in range(1, N):
			dp[i][i] = 0
		for i in range(N - 1, 0, -1):
			for j in range(i + 1, N):
				mini = float('inf')
				for k in range(i, j):
					ans = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					mini = min(mini, ans)
				dp[i][j] = mini
		return dp[1][N - 1]


class Solution:

	def matrixMultiplication(self, n, m):
		dp = [[-1] * (n + 1) for i in range(n + 1)]

		def dfs(m, i, j):
			if dp[i][j] != -1:
				return dp[i][j]
			if i + 1 == j:
				return 0
			mx = float('inf')
			for k in range(i + 1, j):
				t = dfs(m, i, k) + dfs(m, k, j) + m[i] * m[k] * m[j]
				mx = min(mx, t)
			dp[i][j] = mx
			return dp[i][j]
		return dfs(m, 0, n - 1)


class Solution:

	def solve(self, arr, i, j, DPT):
		if i >= j:
			return 0
		if DPT[i][j] != -1:
			return DPT[i][j]
		ans = float('inf')
		for k in range(i, j):
			temp = self.solve(arr, i, k, DPT) + self.solve(arr, k + 1, j, DPT) + arr[i - 1] * arr[k] * arr[j]
			ans = min(ans, temp)
		DPT[i][j] = ans
		return DPT[i][j]

	def matrixMultiplication(self, N, arr):
		DPT = [[-1 for _ in range(N + 1)] for _ in range(N + 1)]
		return self.solve(arr, 1, N - 1, DPT)


from functools import lru_cache

class Solution:

	def matrixMultiplication(self, N, arr):

		@lru_cache(None)
		def help(s, e):
			if s >= e:
				return 0
			if s == e - 1:
				return 0
			if e == s + 2:
				return arr[s] * arr[s + 1] * arr[e]
			ans = float('inf')
			for k in range(s + 1, e):
				tmp = help(s, k) + help(k, e) + arr[s] * arr[k] * arr[e]
				ans = min(ans, tmp)
			return ans
		return help(0, N - 1)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for i in range(501)] for j in range(501)]

		def solve(arr, i, j):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			ans = 10 ** 9
			for k in range(i, j):
				x = solve(arr, i, k)
				y = solve(arr, k + 1, j)
				temp_ans = x + y + arr[i - 1] * arr[k] * arr[j]
				ans = min(temp_ans, ans)
			dp[i][j] = ans
			return ans
		return solve(arr, 1, N - 1)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for _ in range(len(arr))] for _ in range(len(arr))]
		return minMul(arr, 1, N - 1, dp)

def minMul(arr, i, j, dp):
	if i == j:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	minn = float('inf')
	for k in range(i, j):
		step = arr[i - 1] * arr[k] * arr[j] + minMul(arr, i, k, dp) + minMul(arr, k + 1, j, dp)
		minn = min(step, minn)
	dp[i][j] = minn
	return dp[i][j]


class Solution:

	def matrixMultiplication(self, N, arr):
		(i, j) = (0, len(arr) - 2)
		dp = [[-1 for i in range(len(arr) - 1)] for j in range(len(arr) - 1)]
		res = self.mcm(arr, i, j, dp)
		return res

	def mcm(self, arr, i, j, dp):
		if i >= j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		res = float('inf')
		for k in range(i, j):
			res = min(res, arr[i] * arr[k + 1] * arr[j + 1] + self.mcm(arr, i, k, dp) + self.mcm(arr, k + 1, j, dp))
		dp[i][j] = res
		return res


class Solution:

	def solve(self, arr, i, j, N, dp):
		if i == j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		dp[i][j] = float('inf')
		for k in range(i, j):
			dp[i][j] = min(dp[i][j], self.solve(arr, i, k, N, dp) + self.solve(arr, k + 1, j, N, dp) + arr[i - 1] * arr[k] * arr[j])
		return dp[i][j]

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for i in range(N + 1)] for j in range(N + 1)]
		a = self.solve(arr, 1, N - 1, N, dp)
		return a


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[0] * N for _ in range(N)]
		for l in range(2, N):
			for i in range(1, N - l + 1):
				j = i + l - 1
				dp[i][j] = float('inf')
				for k in range(i, j):
					temp = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					dp[i][j] = min(dp[i][j], temp)
		return dp[1][N - 1]


class Solution:

	def matrixMultiplication(self, n, arr):
		dp = [[-1 for i in range(n)] for j in range(n)]
		for i in range(1, n):
			dp[i][i] = 0
		for i in range(n - 1, 0, -1):
			for j in range(i + 1, n):
				mini = int(1000000000.0)
				for k in range(i, j):
					ans = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					mini = min(mini, ans)
				dp[i][j] = mini
		return dp[1][n - 1]


class Solution:

	def matrixMultiplication(self, n, arr):
		dp = [[-1 for i in range(n)] for j in range(n)]

		def answer(i, j):
			if i == j:
				return 0
			mini = int(1000000000.0)
			if dp[i][j] != -1:
				return dp[i][j]
			for k in range(i, j):
				steps = arr[i - 1] * arr[k] * arr[j] + answer(i, k) + answer(k + 1, j)
				mini = min(mini, steps)
			dp[i][j] = mini
			return mini
		g = answer(1, n - 1)
		return g


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for _ in range(N + 2)] for _ in range(N + 2)]

		def helper(i, j):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			ans = int(1000000000.0)
			for k in range(i, j):
				temp = helper(i, k) + helper(k + 1, j) + arr[i - 1] * arr[k] * arr[j]
				ans = min(temp, ans)
			dp[i][j] = ans
			return dp[i][j]
		res = helper(1, N - 1)
		return res


class Solution:
	dp = []

	def gen(self, i, j, arr):
		if i == j:
			return 0
		if self.dp[i][j] != -1:
			return self.dp[i][j]
		mini = 9999999999999
		for k in range(i, j):
			ans = arr[i - 1] * arr[k] * arr[j] + self.gen(i, k, arr) + self.gen(k + 1, j, arr)
			mini = min(mini, ans)
		self.dp[i][j] = mini
		return mini

	def matrixMultiplication(self, n, arr):
		self.dp = []
		for i in range(n):
			a = []
			for j in range(n):
				a.append(-1)
			self.dp.append(a)
		return self.gen(1, n - 1, arr)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for i in range(100)] for j in range(100)]

		def matrixChainMemoised(p, i, j):
			if i == j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = float('inf')
			for k in range(i, j):
				dp[i][j] = min(dp[i][j], matrixChainMemoised(p, i, k) + matrixChainMemoised(p, k + 1, j) + p[i - 1] * p[k] * p[j])
			return dp[i][j]
		return matrixChainMemoised(arr, 1, N - 1)


import math

class Solution:

	def matrixMultiplication(self, N, arr):

		def solve(i, j):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			minval = math.inf
			for k in range(i, j):
				temp = solve(i, k) + solve(k + 1, j) + arr[i - 1] * arr[k] * arr[j]
				minval = min(minval, temp)
			dp[i][j] = minval
			return dp[i][j]
		dp = [[-1] * (N + 2) for _ in range(N + 2)]
		ans = solve(1, N - 1)
		return ans


import sys
import numpy as np

class Solution:

	def rec_sol(self, start, end, Arr):
		if start + 1 == end:
			return 0
		mina = sys.maxsize
		for i in range(start + 1, end):
			mina = min(mina, Arr[start] * Arr[end] * Arr[i] + self.rec_sol(start, i, Arr) + self.rec_sol(i, end, Arr))
		return mina

	def mem_sol(self, start, end, Arr, dp):
		if start + 1 == end:
			return 0
		if dp[start][end] != -1:
			return dp[start][end]
		mina = sys.maxsize
		for i in range(start + 1, end):
			mina = min(mina, Arr[start] * Arr[end] * Arr[i] + self.mem_sol(start, i, Arr, dp) + self.mem_sol(i, end, Arr, dp))
		dp[start][end] = mina
		return mina

	def dp_sol(self, N, Arr):
		if N <= 2:
			return 0
		dp = np.array([[0] * N] * N)
		for i in range(2, N):
			for j in range(i - 2, -1, -1):
				mina = sys.maxsize
				for k in range(i - 1, j, -1):
					mina = min(mina, Arr[j] * Arr[k] * Arr[i] + dp[j][k] + dp[k][i])
				dp[j][i] = mina
		return dp[0][N - 1]

	def matrixMultiplication(self, N, arr):
		return self.dp_sol(N, arr)


class Solution:

	def matrixMultiplication(self, N, arr):
		d = {}

		def fun(i, j):
			if j - i <= 1:
				return 0
			if (i, j) in d:
				return d[i, j]
			steps = 1e+22
			for k in range(i + 1, j):
				res = arr[i] * arr[j] * arr[k] + fun(i, k) + fun(k, j)
				steps = min(steps, res)
			d[i, j] = steps
			return d[i, j]
		return fun(0, N - 1)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[0 for j in range(len(arr))] for i in range(len(arr))]
		for i in range(len(arr) - 1, 0, -1):
			for j in range(i + 1, len(arr)):
				miniAnswer = float('inf')
				for k in range(i, j):
					steps = arr[i - 1] * arr[k] * arr[j] + dp[i][k] + dp[k + 1][j]
					miniAnswer = min(miniAnswer, steps)
				dp[i][j] = miniAnswer
		return dp[1][len(arr) - 1]


class Solution:

	def ops(self, i, j, arr, dp):
		if i == j:
			return 0
		if dp[i][j] != -1:
			ans = dp[i][j]
			return ans
		mini = 1000000000.0
		for k in range(i, j):
			step1 = self.ops(i, k, arr, dp)
			step2 = self.ops(k + 1, j, arr, dp)
			step3 = arr[i - 1] * arr[k] * arr[j]
			steps = step1 + step2 + step3
			mini = min(dp[i][j], steps)
		dp[i][j] = mini
		return dp[i][j]

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for _ in range(N)] for _ in range(N)]
		for i in range(1, N):
			dp[i][i] = 0
		for i in range(N - 1, 0, -1):
			for j in range(i + 1, N):
				mini = 1000000000.0
				for k in range(i, j):
					steps = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					mini = min(mini, steps)
				dp[i][j] = mini
		return dp[i][N - 1]


class Solution:

	def matrixMultiplication(self, N, arr):
		memo = [[-1 for i in range(N)] for j in range(N)]

		def MCM(start, end):
			if start + 1 >= end:
				return 0
			if memo[start][end] != -1:
				return memo[start][end]
			ans = float('inf')
			for i in range(start + 1, end):
				ans = min(ans, arr[start] * arr[i] * arr[end] + MCM(start, i) + MCM(i, end))
			memo[start][end] = ans
			return ans
		return MCM(0, N - 1)


from functools import lru_cache

class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[0 for i in range(N)] for j in range(N)]
		for i in range(1, N):
			dp[i][i] = 0
		for L in range(2, N):
			for i in range(1, N - L + 1):
				j = i + L - 1
				dp[i][j] = float('inf')
				for k in range(i, j):
					temp = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					dp[i][j] = min(dp[i][j], temp)
		return dp[1][N - 1]


class Solution:

	def matrixMultiplication(self, N, arr):
		cache = [[-1 for _ in range(N)] for _ in range(N)]
		return self.mcm(1, N - 1, arr, cache)

	def mcm(self, i, j, arr, cache):
		if i == j:
			return 0
		if cache[i][j] != -1:
			return cache[i][j]
		minn = float('infinity')
		for partition in range(i, j):
			steps = arr[i - 1] * arr[partition] * arr[j] + self.mcm(i, partition, arr, cache) + self.mcm(partition + 1, j, arr, cache)
			minn = min(minn, steps)
		cache[i][j] = minn
		return minn


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for _ in range(N)] for _ in range(N)]
		return self.f(arr, 1, N - 1, dp)

	def f(self, arr, i, j, dp):
		if i >= j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		res = float('inf')
		for k in range(i, j):
			temp = self.f(arr, i, k, dp) + self.f(arr, k + 1, j, dp) + arr[i - 1] * arr[k] * arr[j]
			res = min(res, temp)
		dp[i][j] = res
		return res


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[float('inf') for j in range(N)] for i in range(N)]
		for i in range(1, N):
			dp[i][i] = 0
		for L in range(1, N):
			for i in range(1, N - L + 1):
				j = i + L - 1
				for k in range(i, j):
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j])
		return dp[1][N - 1]


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for j in range(N)] for i in range(N)]
		return helper(N, arr, 1, N - 1, dp)

def helper(N, arr, i, j, dp):
	if i == j:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	mini = float('inf')
	for k in range(i, j):
		count = helper(N, arr, i, k, dp) + helper(N, arr, k + 1, j, dp) + arr[i - 1] * arr[k] * arr[j]
		mini = min(mini, count)
	dp[i][j] = mini
	return dp[i][j]


class Solution:

	def matrixMultiplication(self, N, arr):

		def solve(arr, i, j, dp):
			if i == j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			min1 = float('inf')
			for k in range(i, j):
				temp = solve(arr, i, k, dp) + solve(arr, k + 1, j, dp) + arr[i - 1] * arr[j] * arr[k]
				if min1 > temp:
					min1 = temp
				dp[i][j] = min1
			return min1
		dp = [[-1] * N for _ in range(N)]
		return solve(arr, 1, len(arr) - 1, dp)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[0 for i in range(N + 2)] for i in range(N + 2)]
		MAX = 1 << 33
		for L in range(2, N):
			for i in range(1, N - L + 1):
				j = i + L - 1
				dp[i][j] = MAX
				for k in range(i, j):
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j])
		return dp[1][N - 1]


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for _ in range(N + 1)] for _ in range(N + 1)]

		def helper(i, j):
			if i == j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			min_val = float('inf')
			for k in range(i, j):
				value = arr[i - 1] * arr[k] * arr[j] + helper(i, k) + helper(k + 1, j)
				min_val = min(min_val, value)
			dp[i][j] = min_val
			return min_val
		return helper(1, N - 1)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for i in range(N + 2)] for j in range(N + 2)]

		def sol(i, j):
			if i >= j:
				return 0
			mn = int(1000000000.0)
			if dp[i][j] != -1:
				return dp[i][j]
			for k in range(i, j):
				t = sol(i, k) + sol(k + 1, j) + arr[i - 1] * arr[k] * arr[j]
				mn = min(mn, t)
			dp[i][j] = mn
			return mn
		x = sol(1, N - 1)
		return x


class Solution:

	def mem(self, dp, N, arr, i, j):
		if j - i <= 1:
			dp[i][j] = 0
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		cost = 2147483647
		for k in range(i + 1, j):
			cost = min(cost, arr[i] * arr[k] * arr[j] + self.mem(dp, N, arr, i, k) + self.mem(dp, N, arr, k, j))
		dp[i][j] = cost
		return cost

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for j in range(N + 1)] for i in range(N + 1)]
		return self.mem(dp, N, arr, 0, N - 1)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for i in range(N + 2)] for j in range(N + 2)]

		def solve(i, j):
			if i >= j:
				return 0
			ans = 999999999
			if dp[i][j] != -1:
				return dp[i][j]
			for k in range(i, j):
				temp = solve(i, k) + solve(k + 1, j) + arr[i - 1] * arr[k] * arr[j]
				ans = min(ans, temp)
			dp[i][j] = ans
			return ans
		x = solve(1, N - 1)
		return x


class Solution:

	def matrixMultiplication(self, N, arr):
		if N <= 2:
			return 0
		mTable = [[0 for _ in range(N)] for i in range(N)]

		def dfs(start, end):
			if mTable[start][end]:
				return mTable[start][end]
			if start > end:
				mTable[start][end] = 0
				return mTable[start][end]
			minVal = float('inf')
			for i in range(start, end + 1):
				minVal = min(minVal, arr[start - 1] * arr[i] * arr[end + 1] + dfs(start, i - 1) + dfs(i + 1, end))
			mTable[start][end] = minVal
			return mTable[start][end]
		return dfs(1, N - 2)


class Solution:

	def solve(self, i, j, arr, dp):
		if i == j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		minCost = float('inf')
		for k in range(i, j):
			cost = self.solve(i, k, arr, dp) + self.solve(k + 1, j, arr, dp) + arr[i - 1] * arr[k] * arr[j]
			minCost = min(minCost, cost)
		dp[i][j] = minCost
		return dp[i][j]

	def matrixMultiplication(self, N, arr):
		dp = []
		for i in range(N):
			c = []
			for j in range(N):
				c.append(-1)
			dp.append(c)
		return self.solve(1, N - 1, arr, dp)


from functools import lru_cache

class Solution:

	def matrixMultiplication(self, N, arr):

		@lru_cache(None)
		def solve(i, j):
			if i >= j - 1:
				return 0
			ans = float('inf')
			for k in range(i + 1, j):
				ans = min(ans, solve(i, k) + solve(k, j) + arr[i] * arr[k] * arr[j])
			return ans
		return solve(0, N - 1)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for i in range(len(arr))] for j in range(len(arr))]
		return self.mcm(arr, 1, len(arr) - 1, dp)

	def mcm(self, lst, i, j, dp):
		if i == j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		mini = 1000000000.0
		for k in range(i, j):
			steps = lst[i - 1] * lst[k] * lst[j] + self.mcm(lst, i, k, dp) + self.mcm(lst, k + 1, j, dp)
			if steps < mini:
				mini = steps
		dp[i][j] = mini
		return mini


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[0 for i in range(N)] for j in range(N)]
		for idx in range(N - 1, 0, -1):
			for last in range(idx + 1, N):
				maxi = float('inf')
				for i in range(idx, last):
					temp = arr[last] * arr[i] * arr[idx - 1] + dp[idx][i] + dp[i + 1][last]
					maxi = min(maxi, temp)
				dp[idx][last] = maxi
		return dp[1][N - 1]


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1] * N for i in range(N)]
		for i in range(N):
			dp[i][i] = 0
		for i in range(N - 1, 0, -1):
			for j in range(i + 1, N):
				mini = pow(2, 30)
				for k in range(i, j):
					ans = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					mini = min(mini, ans)
				dp[i][j] = mini
		return dp[1][N - 1]


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for i in range(N + 2)] for j in range(N + 2)]

		def solve(i, j):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			mn = int(1000000000.0)
			for k in range(i, j):
				t = solve(i, k) + solve(k + 1, j) + arr[i - 1] * arr[k] * arr[j]
				if t < mn:
					mn = t
			dp[i][j] = mn
			return mn
		a = solve(1, N - 1)
		return a


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[-1 for i in range(N)] for j in range(N)]
		for i in range(N):
			dp[i][i] = 0
		for i in range(N - 1, 0, -1):
			for j in range(i + 1, N):
				ans = 1000000000.0
				for k in range(i, j):
					steps = arr[i - 1] * arr[k] * arr[j] + dp[i][k] + dp[k + 1][j]
					if steps < ans:
						ans = steps
				dp[i][j] = ans
		return dp[1][N - 1]


import math

class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[0] * N for _ in range(N)]
		for i in range(N - 1, 0, -1):
			for j in range(i + 1, N):
				minCost = math.inf
				for k in range(i, j):
					cost = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					minCost = min(minCost, cost)
				dp[i][j] = minCost
		return dp[1][N - 1]


import sys
from functools import lru_cache

class Solution:

	def matrixMultiplication(self, N, arr):
		num_matrices = N - 1

		@lru_cache(None)
		def MCU(l, r):
			if l == r:
				return 0
			cost = sys.maxsize
			for i in range(l, r):
				curr = MCU(l, i) + MCU(i + 1, r) + arr[l] * arr[r + 1] * arr[i + 1]
				cost = min(cost, curr)
			return cost
		return MCU(0, num_matrices - 1)


class Solution:

	@staticmethod
	def matrixMultiplication(N, arr):
		dp = [[0 for i in range(N)] for j in range(N)]
		for i in range(N - 1, 0, -1):
			for j in range(i + 1, N):
				dp[i][j] = float('inf')
				for k in range(i, j):
					cost = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					dp[i][j] = min(dp[i][j], cost)
		return dp[1][N - 1]


class Solution:

	def matrixMultiplication(self, n, arr):
		dp = {}

		def fun(i=1, j=n - 1):
			if i == j:
				return 0
			if (i, j) in dp:
				return dp[i, j]
			mini = float('inf')
			for k in range(i, j):
				res = arr[i - 1] * arr[k] * arr[j] + fun(i, k) + fun(k + 1, j)
				mini = min(mini, res)
			dp[i, j] = mini
			return mini
		return fun()


class Solution:

	def matrixMultiplication(self, N, arr):

		def findans(arr, start, end):
			if start == end:
				return 0
			ans = float('inf')
			for k in range(start, end):
				ans = min(ans, arr[start - 1] * arr[k] * arr[end] + findans(arr, start, k) + findans(arr, k + 1, end))
			return ans
		dp = [[float('inf')] * N for i in range(N)]
		steps = float('inf')
		for i in range(N):
			dp[i][i] = 0
		for start in range(N - 1, 0, -1):
			for end in range(start + 1, N):
				for k in range(start, end):
					dp[start][end] = min(dp[start][end], arr[start - 1] * arr[k] * arr[end] + dp[start][k] + dp[k + 1][end])
					steps = min(steps, dp[start][end])
		return dp[1][N - 1]


import sys

class Solution:

	def matrixMultiplication(self, N, arr):
		m = [[0 for x in range(N)] for x in range(N)]
		for i in range(1, N):
			m[i][i] = 0
		for L in range(2, N):
			for i in range(1, N - L + 1):
				j = i + L - 1
				m[i][j] = sys.maxsize
				for k in range(i, j):
					q = m[i][k] + m[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					if q < m[i][j]:
						m[i][j] = q
		return m[1][N - 1]


import math

class Solution:

	def matrixMultiplication(self, N, arr):
		d = [[-1 for i in range(N + 1)] for j in range(N + 1)]

		def mcm(i, j):
			if j == i:
				return 0
			if d[i][j] != -1:
				return d[i][j]
			m = math.inf
			for k in range(i + 1, j):
				x = mcm(i, k) + arr[i] * arr[k] * arr[j] + mcm(k, j)
				m = min(m, x)
			if m == math.inf:
				d[i][j] = 0
				return 0
			d[i][j] = m
			return m
		return mcm(0, N - 1)


class Solution:

	def matrixMultiplication(self, N, arr):
		maxi = 10 ** 10
		dp = [[-1] * N for _ in range(N)]

		def find(i, j):
			if j == i:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			ans = maxi
			for k in range(i, j):
				x = find(i, k) + find(k + 1, j) + arr[i - 1] * arr[k] * arr[j]
				ans = min(ans, x)
			dp[i][j] = ans
			return dp[i][j]
		return find(1, N - 1)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[0 for i in range(N + 2)] for j in range(N + 2)]

		def solve(arr, i, j):
			if i >= j:
				return 0
			if dp[i][j] != 0:
				return dp[i][j]
			mini = float('inf')
			for k in range(i, j):
				tem = solve(arr, i, k) + solve(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j]
				mini = min(mini, tem)
			dp[i][j] = mini
			return dp[i][j]
		return solve(arr, 1, N - 1)


import sys

class Solution:

	def matrixMultiplication(self, N, arr):
		n = len(arr)
		dp = [[0] * n for _ in range(n)]
		for i in range(n - 2, -1, -1):
			for j in range(i + 1, n):
				minn = sys.maxsize
				for k in range(i, j):
					temp = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					minn = min(temp, minn)
				dp[i][j] = minn
		return dp[1][n - 1]


import sys
maxint = int(1000000000.0 + 7)

class Solution:

	def matrixMultiplication(self, N, arr):
		m = [[0 for x in range(N)] for x in range(N)]
		for i in range(1, N):
			m[i][i] = 0
		for L in range(2, N):
			for i in range(1, N - L + 1):
				j = i + L - 1
				m[i][j] = maxint
				for k in range(i, j):
					q = m[i][k] + m[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					if q < m[i][j]:
						m[i][j] = q
		return m[1][N - 1]


import sys

class Solution:

	def matrixMultiplication(self, N, arr):

		def fun(arr, i, j):
			if i == j:
				return 0
			mini = sys.maxsize
			if dp[i][j] != -1:
				return dp[i][j]
			for k in range(i, j):
				tempans = fun(arr, i, k) + fun(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j]
				mini = min(mini, tempans)
				dp[i][j] = mini
			return dp[i][j]
		dp = [[-1 for i in range(1, len(arr) + 1)] for j in range(1, len(arr) + 1)]
		return fun(arr, 1, len(arr) - 1)


class Solution:

	def matrixMultiplication(self, n, p):
		m = [[0 for x in range(n)] for x in range(n)]
		for i in range(1, n):
			m[i][i] = 0
		for L in range(2, n):
			for i in range(1, n - L + 1):
				j = i + L - 1
				m[i][j] = int(1000000000.0 + 7)
				for k in range(i, j):
					q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
					if q < m[i][j]:
						m[i][j] = q
		return m[1][n - 1]


from math import inf

class Solution:

	def matrixMultiplication(self, n, x):
		dp = {}

		def f(i, j):
			if j - i <= 1:
				return 0
			if (i, j) in dp:
				return dp[i, j]
			ans = inf
			for k in range(i + 1, j):
				ans = min(ans, f(i, k) + f(k, j) + x[i] * x[j] * x[k])
			dp[i, j] = ans
			return ans
		return f(0, n - 1)


class Solution:

	def matrixMultiplication(self, N, arr):
		dp = [[0] * N for i in range(N)]
		for i in range(1, N):
			dp[i][i] = 0
		for l in range(2, N):
			for i in range(1, N - l + 1):
				j = i + l - 1
				dp[i][j] = 10000000000.0
				for k in range(i, j):
					one = dp[i][k]
					two = dp[k + 1][j]
					temp_ans = one + two + arr[i - 1] * arr[k] * arr[j]
					dp[i][j] = min(dp[i][j], temp_ans)
		return dp[1][N - 1]


import math

class Solution:

	def matrixMultiplication(self, N, arr):
		t = [[0 for i in range(N)] for j in range(N)]
		for i in range(1, N):
			t[i][i] = 0
		for i in range(N - 1, -1, -1):
			for j in range(i + 1, N):
				mini = math.inf
				for k in range(i, j):
					ans = t[i][k] + t[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					mini = min(mini, ans)
				t[i][j] = mini
		return t[1][N - 1]


import sys

class Solution:

	def matrixMultiplication(self, N, arr):
		t = [[0 for i in range(N)] for j in range(N)]
		for i in range(1, N):
			t[i][i] = 0
		for i in range(N - 1, -1, -1):
			for j in range(i + 1, N):
				mini = sys.maxsize
				for k in range(i, j):
					ans = t[i][k] + t[k + 1][j] + arr[i - 1] * arr[k] * arr[j]
					mini = min(mini, ans)
				t[i][j] = mini
		return t[1][N - 1]


class Solution:

	def matrixMultiplication(self, n, arr):
		dp = [[0 for _ in range(n)] for _ in range(n)]
		for L in range(2, n + 1):
			for i in range(1, n - L + 1):
				j = i + L - 1
				dp[i][j] = float('inf')
				for k in range(i, j):
					dp[i][j] = min(dp[i][j], arr[i - 1] * arr[k] * arr[j] + dp[i][k] + dp[k + 1][j])
		return dp[1][n - 1]