Given an array arr of positive integers, consider all binary trees such that:

Each node has either 0 or 2 children;
The values of arr correspond to the values of each leaf in an in-order traversal of the tree.  (Recall that a node is a leaf if and only if it has 0 children.)
The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node.  It is guaranteed this sum fits into a 32-bit integer.
 
Example 1:
Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4

 
Constraints:

2 <= arr.length <= 40
1 <= arr[i] <= 15
It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        

Solutions:
class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		if not arr:
			return 0
		res = []
		while len(arr) > 1:
			temp_res = []
			temp_res = [arr[i] * arr[i + 1] for i in range(len(arr) - 1)]
			idx = temp_res.index(min(temp_res))
			res.append(temp_res[idx])
			arr.pop(idx if arr[idx] < arr[idx + 1] else idx + 1)
		return sum(res)


class Solution:

	def mctFromLeafValues(self, A: List[int]) -> int:
		res = 0
		while len(A) > 1:
			i = A.index(min(A))
			neighbors = []
			if i - 1 >= 0:
				neighbors.append(A[i - 1])
			if i + 1 < len(A):
				neighbors.append(A[i + 1])
			res += min(neighbors) * A.pop(i)
		return res


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		res = 0
		while len(arr) > 1:
			mini_idx = arr.index(min(arr))
			if 0 < mini_idx < len(arr) - 1:
				res += min(arr[mini_idx - 1], arr[mini_idx + 1]) * arr[mini_idx]
			else:
				res += arr[1 if mini_idx == 0 else mini_idx - 1] * arr[mini_idx]
			arr.pop(mini_idx)
		return res


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		if len(arr) <= 1:
			return 0
		min_i = 0
		min_val = arr[0] * arr[1]
		for i in range(1, len(arr) - 1):
			cur = arr[i] * arr[i + 1]
			if cur < min_val:
				min_val = cur
				min_i = i
		new_arr = arr[:min_i] + [max(arr[min_i], arr[min_i + 1])] + arr[min_i + 2:]
		return min_val + self.mctFromLeafValues(new_arr)


class Solution:

	def helper(self, arr):
		if not arr:
			pass
		elif len(arr) == 1:
			return 0
		else:
			res = sys.maxsize
			max_ind = arr.index(max(arr))
			for div in range(max_ind, max_ind + 2):
				temp_res = 0
				if div == 0 or div == len(arr):
					continue
				temp_res += max(arr[:div]) * max(arr[div:])
				temp_res += self.helper(arr[:div])
				temp_res += self.helper(arr[div:])
				res = min(res, temp_res)
			return res

	def mctFromLeafValues(self, arr: List[int]) -> int:
		return self.helper(arr)


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		res = 0
		while len(arr) > 1:
			idx = arr.index(min(arr))
			if 0 < idx < len(arr) - 1:
				res += min(arr[idx - 1], arr[idx + 1]) * arr[idx]
				arr = arr[:idx] + arr[idx + 1:]
			elif idx == 0:
				res += arr[1] * arr[idx]
				arr = arr[1:]
			else:
				res += arr[-2] * arr[idx]
				arr = arr[:-1]
		return res


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		stack = [arr[0]]
		_sum = 0
		for n in arr[1:]:
			while stack and n > stack[-1]:
				n1 = stack.pop()
				n2 = n if not stack or n < stack[-1] else stack[-1]
				_sum += n1 * n2
			stack.append(n)
		while len(stack) > 1:
			n1 = stack.pop()
			n2 = stack.pop()
			_sum += n1 * n2
			if not stack:
				break
			stack.append(max(n1, n2))
		return _sum


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		res = 0
		while len(arr) > 1:
			mid = arr.index(min(arr))
			res += min(arr[mid - 1:mid] + arr[mid + 1:mid + 2]) * arr.pop(mid)
		return res


class Solution:

	def mctFromLeafValues(self, arr):
		vals = [[0] * len(arr) for i in range(len(arr))]
		maxes = [[0] * len(arr) for i in range(len(arr))]
		for n in range(1, len(arr) + 1):
			for a in range(len(arr) - n + 1):
				b = a + n
				maxes[a][b - 1] = max(maxes[a][b - 2], arr[b - 1])
				if n >= 2:
					vals[a][b - 1] = min((vals[a][i - 1] + vals[i][b - 1] + maxes[a][i - 1] * maxes[i][b - 1] for i in range(a + 1, b)))
		print(vals)
		return vals[0][len(arr) - 1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		dp = [[0 for i in range(len(arr))] for j in range(len(arr))]
		for i in range(len(arr)):
			dp[i][i] = (0, arr[i])
		for v in range(1, len(arr)):
			for j in range(v, len(arr)):
				i = j - v
				D_i_j = min((dp[i][k][0] + dp[k + 1][j][0] + dp[i][k][1] * dp[k + 1][j][1] for k in range(i, j)))
				M_i_j = max(dp[i][j - 1][1], arr[j])
				dp[i][j] = (D_i_j, M_i_j)
		return dp[0][len(arr) - 1][0]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		max_dp = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			temp = arr[i]
			for j in range(i, n):
				temp = max(temp, arr[j])
				max_dp[i][j] = temp
		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):
			dp[i][i + 1] = arr[i] * arr[i + 1]
		for k in range(2, n):
			for i in range(n):
				j = i + k
				if j >= n:
					break
				dp[i][j] = dp[i][i] + dp[i + 1][j] + arr[i] * max_dp[i + 1][j]
				for s in range(i + 1, j):
					dp[i][j] = min(dp[i][j], dp[i][s] + dp[s + 1][j] + max_dp[i][s] * max_dp[s + 1][j])
		return dp[0][-1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		dp = [[[0, 0] for _1 in range(n)] for _2 in range(n)]
		for i in range(n):
			dp[i][i] = [arr[i], 0]
		for diff in range(1, n):
			for i in range(n - diff):
				temp_min_ = 10 ** 40
				root = None
				for j in range(i, i + diff):
					sum_ = dp[i][j][1] + dp[j + 1][i + diff][1] + dp[i][j][0] * dp[j + 1][i + diff][0]
					if sum_ < temp_min_:
						temp_min_ = sum_
						root = max(dp[i][j][0], dp[j + 1][i + diff][0])
				dp[i][i + diff] = [root, temp_min_]
		return dp[0][-1][1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		m = [None] * n
		for i in range(len(m)):
			m[i] = [float('-inf')] * n
			m[i][i] = arr[i]
		for l in range(2, n + 1):
			for i in range(0, n - l + 1):
				j = i + l - 1
				mid = (i + j) // 2
				m[i][j] = max(m[i][j], m[i][mid], m[mid + 1][j])
		f = [None] * n
		for i in range(len(f)):
			f[i] = [float('inf')] * n
			f[i][i] = 0
		for l in range(2, n + 1):
			for i in range(0, n - l + 1):
				j = i + l - 1
				for k in range(i, j):
					f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + m[i][k] * m[k + 1][j])
		return f[0][n - 1]


class Solution:

	def mctFromLeafValues(self, arr):
		maxi = [[0 for _ in range(len(arr))] for _ in range(len(arr))]
		for i in range(len(arr)):
			maxi[i][i] = arr[i]
		for l in range(1, len(arr) - 1):
			for i in range(len(arr) - l):
				j = i + l
				maxi[i][j] = max(maxi[i][j - 1], maxi[i + 1][j])
		dp = [[float('Inf') for i in range(len(arr))] for j in range(len(arr))]
		for i in range(len(arr)):
			dp[i][i] = arr[i]
		for l in range(1, len(arr)):
			for i in range(0, len(arr) - l):
				j = i + l
				for k in range(i, j):
					dp[i][j] = min(dp[i][j], (dp[i][k] if i < k else 0) + (dp[k + 1][j] if k + 1 < j else 0) + maxi[i][k] * maxi[k + 1][j])
		return dp[0][len(arr) - 1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		N = len(arr)
		dp = [[[0, i] for i in arr]]
		for l in range(1, N):
			dp.append([])
			for i in range(N - l):
				dp[l].append([sys.maxsize, 0])
				for x in range(i, i + l):
					tmp = dp[x - i][i][0] + dp[i + l - x - 1][x + 1][0] + dp[x - i][i][1] * dp[i + l - x - 1][x + 1][1]
					if tmp < dp[l][i][0]:
						dp[l][i] = [tmp, max(dp[x - i][i][1], dp[i + l - x - 1][x + 1][1])]
		return dp[-1][0][0]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:

		@lru_cache(None)
		def cached_max(i, j):
			return max(arr[i:j] or [1])

		@lru_cache(None)
		def dp(i, j):
			if j - i <= 1:
				return 0
			elif j - i == 2:
				return arr[i] * arr[i + 1]
			return min((dp(i, k) + dp(k, j) + cached_max(i, k) * cached_max(k, j) for k in range(i + 1, j)))
		return dp(0, len(arr))


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:

		def compute(arr, lo, hi, dp):
			if dp[lo][hi] != -1:
				return dp[lo][hi]
			if hi == lo:
				dp[lo][hi] = (0, arr[lo])
				return (0, arr[lo])
			if hi == lo + 1:
				dp[lo][hi] = (arr[lo] * arr[hi], max(arr[lo], arr[hi]))
				return (arr[lo] * arr[hi], max(arr[lo], arr[hi]))
			k = float('inf')
			c = 0
			for i in range(lo, hi):
				left = compute(arr, lo, i, dp)
				right = compute(arr, i + 1, hi, dp)
				t = left[0] + right[0] + left[1] * right[1]
				if t < k:
					k = t
					c = max(left[1], right[1])
			dp[lo][hi] = (k, c)
			return (k, c)
		dp = [[-1] * len(arr) for row in arr]
		x = compute(arr, 0, len(arr) - 1, dp)
		return x[0]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)

		@lru_cache(None)
		def max_cache(a, b):
			return max(arr[a:b])

		@lru_cache(None)
		def dp(i, j):
			n = j - i
			if n == 1:
				return 0
			if n == 2:
				return arr[i] * arr[j - 1]
			min_out = 2 ** 31 - 1
			for k in range(i + 1, j):
				min_out = min(min_out, max_cache(i, k) * max_cache(k, j) + dp(i, k) + dp(k, j))
			return min_out
		return dp(0, n)


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		maximum = [[0 for i in range(len(arr))] for j in range(len(arr))]
		for i in range(len(arr)):
			localMaximum = -math.inf
			for j in range(i, len(arr)):
				localMaximum = max(localMaximum, arr[j])
				maximum[i][j] = localMaximum
		dp = [[math.inf for i in range(len(arr))] for j in range(len(arr))]
		for i in range(len(arr)):
			dp[i][i] = 0
		for length in range(1, len(arr)):
			for left in range(len(arr) - length):
				right = left + length
				if length == 1:
					dp[left][right] = arr[left] * arr[right]
				else:
					for k in range(left, right):
						dp[left][right] = min(dp[left][right], dp[left][k] + dp[k + 1][right] + maximum[left][k] * maximum[k + 1][right])
		return dp[0][len(arr) - 1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		if not arr:
			return 0
		ans = 0
		n = len(arr)
		dp = [[float('inf') for _ in range(n)] for _ in range(n)]
		maxi = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(n):
			dp[i][i] = 0
			maxi[i][i] = arr[i]
		for l in range(1, n + 1):
			for i in range(n - l + 1):
				j = i + l - 1
				for k in range(i, j):
					dp[i][j] = min(dp[i][j], dp[i][k] + maxi[i][k] * maxi[k + 1][j] + dp[k + 1][j])
				for k in range(i, j + 1):
					maxi[i][j] = max(maxi[i][j], arr[k])
		return dp[0][-1]


class Solution:

	def __init__(self):
		self.dict = {}

	def mctFromLeafValues(self, arr: List[int]) -> int:
		return self.mctHelp(arr, 0, len(arr))

	def mctHelp(self, arr, a, b):
		if b - a == 1:
			return 0
		if (a, b) not in self.dict:
			(low, idx) = (2 ** 30, -1)
			for i in range(a + 1, b):
				res = self.mctHelp(arr, a, i) + self.mctHelp(arr, i, b)
				if res < low:
					low = res
					idx = i
			low += max(arr[a:idx]) * max(arr[idx:b])
			self.dict[a, b] = low
		return self.dict[a, b]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		self.cache = {}

		def dp(i, j):
			if (i, j) not in self.cache:
				if i == j:
					ret = (arr[i], 0)
				else:
					(best_p, best_s) = (2 ** 32, 2 ** 32)
					for k in range(i, j):
						(l1, s1) = dp(i, k)
						(l2, s2) = dp(k + 1, j)
						if s1 + s2 + l1 * l2 < best_s:
							best_p = max(l1, l2)
							best_s = s1 + s2 + l1 * l2
					ret = (best_p, best_s)
				self.cache[i, j] = ret
			return self.cache[i, j]
		return dp(0, len(arr) - 1)[-1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		maxs = [[0 if i != j else arr[i] for j in range(n)] for i in range(n)]
		for i in range(n - 1):
			for j in range(i + 1, n):
				for k in range(i, j):
					maxs[i][j] = max(maxs[i][k], maxs[k + 1][j])
					maxs[j][i] = maxs[i][j]
		print(maxs)
		ans = [[0 for j in range(n)] for i in range(n)]
		for l in range(1, n):
			for i in range(n - l):
				j = l + i
				print((i, j))
				ans[i][j] = min((maxs[i][k] * maxs[k + 1][j] + ans[i][k] + ans[k + 1][j] if j - i > 1 else maxs[i][k] * maxs[k + 1][j] for k in range(i, j)))
		print(ans)
		return ans[0][n - 1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		dp = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(n):
			dp[i][i] = 0
		for i in range(n - 1):
			dp[i][i + 1] = arr[i] * arr[i + 1]
		for l in range(2, n + 1):
			for i in range(n - l):
				j = i + l
				dp[i][j] = float('inf')
				for k in range(i + 1, j + 1):
					q = dp[i][k - 1] + dp[k][j] + max(arr[i:k]) * max(arr[k:j + 1])
					if q < dp[i][j]:
						dp[i][j] = q
		return dp[0][-1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		mem = {}

		def dp(i, j):
			if i == j:
				return (0, arr[i])
			if i == j - 1:
				return (arr[i] * arr[j], max(arr[i], arr[j]))
			else:
				if (i, j) in mem:
					return mem[i, j]
				pp = max(arr[i:j + 1])
				minn = 10000000000.0
				for k in range(i, j):
					(l, lm) = dp(i, k)
					(r, rm) = dp(k + 1, j)
					minn = min(minn, l + r + lm * rm)
				mem[i, j] = (minn, pp)
				return mem[i, j]
		return dp(0, n - 1)[0]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		dp = [[0] * len(arr) for i in range(len(arr))]
		for i in range(len(arr) - 1, -1, -1):
			for j in range(i + 1, len(arr)):
				if j - i == 1:
					dp[i][j] = arr[i] * arr[j]
					continue
				m = 2 ** 32
				for k in range(i + 1, j + 1):
					s = max(arr[i:k]) * max(arr[k:j + 1]) + dp[i][k - 1] + dp[k][j]
					if s < m:
						m = s
				dp[i][j] = m
		return dp[0][-1]


class Solution:

	def __init__(self):
		self.vals = None

	def mctFromLeafValues(self, arr):
		self.vals = [[0] * len(arr) for i in range(len(arr))]
		for n in range(2, len(arr) + 1):
			for a in range(len(arr) - n + 1):
				b = a + n
				self.vals[a][b - 1] = min((self.vals[a][i - 1] + self.vals[i][b - 1] + max(arr[a:i]) * max(arr[i:b]) for i in range(a + 1, b)))
		return self.vals[0][len(arr) - 1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		if len(arr) == 0:
			return 0
		elif len(arr) == 1:
			return arr[0]
		dp = {}
		for i in range(len(arr)):
			dp[i, i + 1] = (0, arr[i])
		for length in range(2, len(arr) + 1):
			for i in range(len(arr) - length + 1):
				end = i + length
				minSum = float('inf')
				maxLeafValue = float('-inf')
				for k in range(i + 1, end):
					minSum = min(minSum, dp[i, k][0] + dp[k, end][0] + dp[i, k][1] * dp[k, end][1])
					maxLeafValue = max([maxLeafValue, dp[i, k][1], dp[k, end][1]])
				dp[i, end] = (minSum, maxLeafValue)
		return dp[0, len(arr)][0]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)

		@lru_cache(None)
		def solve(i, j):
			if j - i <= 1:
				return 0
			return min([max(arr[i:k]) * max(arr[k:j]) + solve(i, k) + solve(k, j) for k in range(i + 1, j)])
		return solve(0, n)


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		N = len(arr)
		dp = [[float('inf')] * N for _ in range(N)]
		for i in range(N - 1, -1, -1):
			for j in range(i, N):
				if i == j:
					dp[i][j] = 0
					continue
				for k in range(i, j):
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + max(arr[i:k + 1]) * max(arr[k + 1:j + 1]))
		return dp[0][N - 1]


from functools import lru_cache

class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		N = len(arr)

		@lru_cache(None)
		def dp(l, r):
			if r - l <= 1:
				return 0
			return min((max(arr[l:m]) * max(arr[m:r]) + dp(l, m) + dp(m, r) for m in range(l + 1, r)))
		return dp(0, N)


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		dp = [[0 for j in range(n)] for i in range(n)]
		for i in range(n - 2, -1, -1):
			dp[i][i + 1] = arr[i] * arr[i + 1]
			for j in range(i + 2, n):
				dp[i][j] = float('inf')
				for k in range(i, j):
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + max(arr[i:k + 1]) * max(arr[k + 1:j + 1]))
		return dp[0][n - 1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		dp = [[sys.maxsize] * len(arr) for i in range(len(arr))]
		for i in range(0, len(arr)):
			dp[i][i] = 0
		for length in range(2, len(arr) + 1):
			for i in range(0, len(arr) - length + 1):
				j = i + length - 1
				for k in range(i, j):
					temp = max(arr[i:k + 1]) * max(arr[k + 1:j + 1]) + dp[i][k] + dp[k + 1][j]
					dp[i][j] = min(dp[i][j], temp)
		return dp[0][-1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		dp = [[0 for _ in range(n)] for _ in range(n)]

		def findMax(l, h):
			return max(arr[l:h + 1])
		for l in range(1, n):
			for i in range(n - l):
				j = i + l
				for k in range(i, j):
					tmp = dp[i][k] + dp[k + 1][j] + findMax(i, k) * findMax(k + 1, j)
					dp[i][j] = tmp if dp[i][j] == 0 else min(dp[i][j], tmp)
		return dp[0][-1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		dp = [[float('inf') for i in range(n)] for j in range(n)]
		mem = {}
		m = [[-float('inf') for i in range(n)] for j in range(n)]
		for i in range(n):
			for j in range(i, n):
				if i == j:
					m[i][j] = arr[i]
					continue
				for k in range(i, j + 1):
					m[i][j] = max(m[i][j], arr[k])

		def rec(left, right):
			if right - left == 0:
				return 0
			elif (left, right) in mem:
				return mem[left, right]
			else:
				ans = float('inf')
				for k in range(left, right):
					ans = min(ans, rec(left, k) + rec(k + 1, right) + m[left][k] * m[k + 1][right])
				mem[left, right] = ans
				return ans
		return rec(0, n - 1)


class Solution:

	def mctFromLeafValues(self, a: List[int]) -> int:
		n = len(a)
		cache = [[[-1, -1]] * n for i in range(n)]

		def dp(i, j):
			if i == j:
				return [0, a[i]]
			if cache[i][j] != [-1, -1]:
				return cache[i][j]
			ans = float('inf')
			mx = 0
			for k in range(i, j):
				l = dp(i, k)
				r = dp(k + 1, j)
				mx = max(mx, l[1])
				mx = max(mx, r[1])
				ans = min(ans, l[0] + r[0] + l[1] * r[1])
			cache[i][j] = [ans, mx]
			return [ans, mx]
		return dp(0, n - 1)[0]


class Solution:

	def mctFromLeafValues(self, A: List[int]) -> int:

		@lru_cache(None)
		def dp(i, j):
			if i == j:
				return 0
			min_cost = float('inf')
			for k in range(i, j):
				min_cost = min(min_cost, dp(i, k) + dp(k + 1, j) + max(A[i:k + 1]) * max(A[k + 1:j + 1]))
			return min_cost
		return dp(0, len(A) - 1)


class Solution:

	def ans(self, start, end, arr, dp):
		product = 999999999999999
		maxleaf = -1
		if start == end:
			return (arr[start], 0)
		for i in range(start, end):
			if (start, end) in dp:
				return dp[start, end]
			(a, b) = self.ans(start, i, arr, dp)
			(c, d) = self.ans(i + 1, end, arr, dp)
			maxleaf = max(a, c)
			product = min(product, a * c + b + d)
		dp[start, end] = (maxleaf, product)
		return (maxleaf, product)

	def mctFromLeafValues(self, arr: List[int]) -> int:
		dp = {}
		return self.ans(0, len(arr) - 1, arr, dp)[1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:

		@lru_cache(maxsize=None)
		def helper(start, end):
			if start >= end:
				return 0
			result = float('inf')
			for i in range(start, end):
				rootVal = max(arr[start:i + 1]) * max(arr[i + 1:end + 1])
				result = min(result, rootVal + helper(start, i) + helper(i + 1, end))
			return result
		return helper(0, len(arr) - 1)


class Solution:

	def __init__(self):
		self.vals = None

	def mctFromLeafValues(self, arr: List[int]) -> int:
		self.vals = [[0] * (len(arr) + 1) for i in range(len(arr))]
		return self.mctHelp(arr, 0, len(arr))

	def mctHelp(self, arr, a, b):
		if b - a == 1:
			return 0
		if self.vals[a][b] == 0:
			low = 2 ** 30
			for i in range(a + 1, b):
				res = self.mctHelp(arr, a, i) + self.mctHelp(arr, i, b) + max(arr[a:i]) * max(arr[i:b])
				if res < low:
					low = res
			self.vals[a][b] = low
		return self.vals[a][b]


import numpy as np

class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)
		dp = np.diag(arr)
		for distance in range(1, n):
			for i in range(n - distance):
				if dp[i + distance - 1, i] <= dp[i + distance, i + distance]:
					dp[i + distance, i] = dp[i + distance, i + distance]
				else:
					dp[i + distance, i] = dp[i + distance - 1, i]
				if distance == 1:
					minvalue = dp[i, i] * dp[i + distance, i + 1]
				else:
					minvalue = dp[i, i] * dp[i + distance, i + 1] + dp[i + 1, i + distance]
				for j in range(1, distance):
					if j == distance - 1:
						tempvalue = dp[i + j, i] * dp[i + distance, i + j + 1] + dp[i, i + j]
					else:
						tempvalue = dp[i + j, i] * dp[i + distance, i + j + 1] + dp[i, i + j] + dp[i + j + 1, i + distance]
					if tempvalue <= minvalue:
						minvalue = tempvalue
				dp[i, i + distance] = minvalue
		return dp[0, n - 1]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		n = len(arr)

		def partition(arr, left, right, cache):
			if (left, right) in cache:
				return cache[left, right]
			if left >= right:
				return 0
			result = sys.maxsize
			for k in range(left, right):
				root_val = max(arr[left:k + 1]) * max(arr[k + 1:right + 1])
				result = min(result, root_val + partition(arr, left, k, cache) + partition(arr, k + 1, right, cache))
			cache[left, right] = result
			return result
		cache = {}
		partition(arr, 0, n - 1, cache)
		return cache[0, n - 1]


class Solution:

	def max(self, arr, l, r):
		a = max(arr[l:r])
		self.mdp[l, r] = a
		return a

	def maxDp(self, arr, l, r):
		a = self.mdp.get((l, r), None)
		return self.max(arr, l, r) if a is None else a

	def mctFromSubArray(self, arr: List[int], l: int, r: int) -> int:
		if l == r - 1:
			return 0
		if l == r - 2:
			return arr[l] * arr[l + 1]
		return min((self.maxDp(arr, l, k) * self.maxDp(arr, k, r) + self.mctFromSubArrayDp(arr, l, k) + self.mctFromSubArrayDp(arr, k, r) for k in range(l + 1, r)))

	def mctFromSubArrayDp(self, arr: List[int], l: int, r: int) -> int:
		if (l, r) in self.dp:
			return self.dp[l, r]
		ans = self.mctFromSubArray(arr, l, r)
		self.dp[l, r] = ans
		return ans

	def mctFromLeafValues(self, arr: List[int]) -> int:
		self.dp = {}
		self.mdp = {}
		return self.mctFromSubArrayDp(arr, 0, len(arr))


class Solution:

	def mctFromSubArray(self, arr: List[int], l: int, r: int) -> int:
		if l == r - 1:
			return 0
		if l == r - 2:
			return arr[l] * arr[l + 1]
		return min((max(arr[l:k]) * max(arr[k:r]) + self.mctFromSubArrayDp(arr, l, k) + self.mctFromSubArrayDp(arr, k, r) for k in range(l + 1, r)))

	def mctFromSubArrayDp(self, arr: List[int], l: int, r: int) -> int:
		if (l, r) in self.dp:
			return self.dp[l, r]
		ans = self.mctFromSubArray(arr, l, r)
		self.dp[l, r] = ans
		return ans

	def mctFromLeafValues(self, arr: List[int]) -> int:
		self.dp = {}
		return self.mctFromSubArrayDp(arr, 0, len(arr))


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		return self.helper(arr, 0, len(arr) - 1, {})

	def helper(self, arr, l, r, cache):
		if (l, r) in cache:
			return cache[l, r]
		if l >= r:
			return 0
		res = float('inf')
		for i in range(l, r):
			rootVal = max(arr[l:i + 1]) * max(arr[i + 1:r + 1])
			res = min(res, rootVal + self.helper(arr, l, i, cache) + self.helper(arr, i + 1, r, cache))
		cache[l, r] = res
		return res


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		self.memo = {}

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


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		res = 0
		stack = [float('inf')]
		for a in arr:
			while stack[-1] <= a:
				m = stack.pop()
				res += m * min(a, stack[-1])
			stack.append(a)
		while len(stack) > 2:
			res += stack.pop() * stack[-1]
		return res


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		return self.mctHelp(arr, 0, len(arr), {})

	def mctHelp(self, arr, a, b, dic):
		if b - a == 1:
			dic[a, b] = 0
		if (a, b) not in dic:
			low = 2 ** 31
			for i in range(a + 1, b):
				res = max(arr[a:i]) * max(arr[i:b]) + self.mctHelp(arr, a, i, dic) + self.mctHelp(arr, i, b, dic)
				low = min(low, res)
			dic[a, b] = low
		return dic[a, b]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		table = {}

		def compute(lo, hi):
			if hi - lo == 1:
				return 0
			cost = float('inf')
			for i in range(lo + 1, hi):
				(left_key, right_key) = (f'{lo}-{i}', f'{i}-{hi}')
				if table.get(left_key) is None:
					table[left_key] = compute(lo, i)
				if table.get(right_key) is None:
					table[right_key] = compute(i, hi)
				cost = min(cost, table[left_key] + table[right_key] + max(arr[lo:i]) * max(arr[i:hi]))
			return cost
		return compute(0, len(arr))


import math

class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:
		self.memo = {}

		def dp(i, j):
			if i == j:
				self.memo[i, j] = [0, arr[i]]
				return self.memo[i, j]
			if (i, j) in self.memo:
				return self.memo[i, j]
			else:
				local_max = -math.inf
				local_sum = math.inf
				for k in range(i, j):
					[left_sum, left_max] = dp(i, k)
					[right_sum, right_max] = dp(k + 1, j)
					local_max = max(local_max, left_max, right_max)
					local_sum = min(local_sum, left_sum + right_sum + left_max * right_max)
				self.memo[i, j] = [local_sum, local_max]
				return self.memo[i, j]
		return dp(0, len(arr) - 1)[0]


class Solution:

	def mctFromLeafValues(self, arr: List[int]) -> int:

		def to_remove():
			cur_min = arr[0] * arr[1]
			res = 0 if arr[0] < arr[1] else 1
			for i in range(len(arr) - 1):
				if arr[i] * arr[i + 1] < cur_min:
					cur_min = arr[i] * arr[i + 1]
					res = i if arr[i] < arr[i + 1] else i + 1
			return res
		res = 0
		while len(arr) > 1:
			i = to_remove()
			res += min(arr[i - 1:i] + arr[i + 1:i + 2]) * arr.pop(i)
		return res
		res = 0
		while len(arr) > 1:
			i = arr.index(min(arr))
			res += min(arr[i - 1:i] + arr[i + 1:i + 2]) * arr.pop(i)
			print(res, arr)
		return res