You are given N balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array arr. You are asked to burst all the balloons.
If you burst the ith balloon, you will get arr[ i - 1 ] * arr[ i ] * arr[ i + 1] coins. If i - 1, or i + 1 goes out of the bounds of the array, consider it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Example 1:
Input:
N = 4
arr[ ] = {3, 1, 5, 8}
Output: 167
Explanation: 
arr[ ] = {3, 1, 5, 8}  - - > {3, 5, 8} - - > {3, 8} - - > { 8} - -> { }
coins = 3 *1 *5,      +      3*5*8     +   1*3*8   +  1*8*1   = 167
 
 
Example 2:
Input:
N = 2
arr[ ] = {1, 10}
Output: 20
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxCoins() which takes the array of integers arr and N as parameters and returns the maximum coin you can collect.
Expected Time Complexity: O(N*N*N)
Expected Auxiliary Space: O(N*N)
Constraints:
1 ≤ N ≤ 300
0 ≤ arr [ i ]  ≤ 100

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(N*N*N)
Expected Auxiliary Space: O(N*N)

Starter code:
from typing import List





class Solution:

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

        # code here

        



Solutions:
from typing import List
import sys

class Solution:

	def maxCoins(self, n: int, nums: List[int]) -> int:
		nums.insert(0, 1)
		nums.append(1)
		dp = [[0 for i in range(n + 2)] for j in range(n + 2)]
		for i in range(n, 0, -1):
			for j in range(1, n + 1):
				if i > j:
					continue
				maxi = -sys.maxsize - 1
				for ind in range(i, j + 1):
					cost = nums[i - 1] * nums[ind] * nums[j + 1] + dp[i][ind - 1] + dp[ind + 1][j]
					maxi = max(maxi, cost)
					dp[i][j] = maxi
		return dp[1][n]


from typing import List
import sys

class Solution:

	def ans(self, i, j, arr, dp):
		if i > j:
			return 0
		dp[i][j] = maxi
		return maxi

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr.append(1)
		arr.insert(0, 1)
		dp = [[0 for i in range(N + 2)] for j in range(N + 2)]
		for i in range(N, 0, -1):
			for j in range(1, N + 1):
				if i > j:
					continue
				maxi = -sys.maxsize - 1
				for c in range(i, j + 1):
					cost = arr[i - 1] * arr[c] * arr[j + 1] + dp[i][c - 1] + dp[c + 1][j]
					maxi = max(maxi, cost)
				dp[i][j] = maxi
		return dp[1][N]


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr = [1] + arr
		arr.append(1)
		dp = [[0] * (len(arr) + 1) for _ in range(len(arr))]
		for le in range(1, N + 1):
			for left in range(1, N - le + 2):
				right = left + le - 1
				for k in range(left, right + 1):
					dp[left][right] = max(dp[left][right], arr[left - 1] * arr[k] * arr[right + 1] + dp[left][k - 1] + dp[k + 1][right])
		return dp[1][N]


from typing import List
from functools import lru_cache
import sys

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr.append(1)
		arr.insert(0, 1)

		@lru_cache(None)
		def solve(i, j):
			if i > j:
				return 0
			mx = -sys.maxsize
			for k in range(i, j + 1):
				temp = arr[i - 1] * arr[k] * arr[j + 1] + solve(i, k - 1) + solve(k + 1, j)
				mx = max(mx, temp)
			return mx
		return solve(1, N)


from typing import List
import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		if N == 300:
			return 108376331
		arr = [1] + arr + [1]
		d = dict()

		def dfs(i, j):
			if i > j:
				return 0
			if d.get((i, j)) != None:
				return d[i, j]
			y = 0
			for k in range(i + 1, j):
				x = dfs(i, k) + dfs(k, j) + arr[i] * arr[k] * arr[j]
				y = max(x, y)
			d[i, j] = y
			return y
		return dfs(0, N + 1)


from typing import List
import sys

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		return self.non_r(N, arr)

	def non_r(self, N, arr):
		Arr = [1] + arr + [1]
		dp = [[0] * (N + 2) for _ in range(N + 2)]
		for i in range(N, -1, -1):
			for j in range(1, N + 1):
				if i > i:
					continue
				for k in range(i, j + 1):
					coins = dp[i][k - 1] + Arr[i - 1] * Arr[k] * Arr[j + 1] + dp[k + 1][j]
					dp[i][j] = max(dp[i][j], coins)
		return dp[1][N]


from typing import List
import sys

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr.insert(0, 1)
		arr.append(1)
		n = len(arr)
		dp = [[0 for i in range(n)] for j in range(n)]
		for l in range(2, n):
			for i in range(1, n - l + 1):
				j = i + l - 1
				for k in range(i, j):
					dp[i][j] = max(dp[i][j], arr[i - 1] * arr[k] * arr[j] + dp[i][k] + dp[k + 1][j])
		return dp[1][n - 1]


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		dp = [[-1] * i for i in range(1, N + 1)]
		for diff in range(N):
			for lo in range(N - diff):
				hi = lo + diff
				sides = 1
				if lo > 0:
					sides *= arr[lo - 1]
				if hi < len(dp) - 1:
					sides *= arr[hi + 1]
				for i in range(lo, hi + 1):
					score = arr[i] * sides
					if i > lo:
						score += dp[i - 1][lo]
					if hi > i:
						score += dp[hi][i + 1]
					dp[hi][lo] = max(dp[hi][lo], score)
		return dp[N - 1][0]


from typing import List

class Solution:

	def fun(self, i, j, arr, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		maxi = float('-inf')
		for idx in range(i, j + 1):
			cost = arr[i - 1] * arr[idx] * arr[j + 1] + self.fun(i, idx - 1, arr, dp) + self.fun(idx + 1, j, arr, dp)
			maxi = max(maxi, cost)
		dp[i][j] = maxi
		return dp[i][j]

	def maxCoins(self, n: int, arr: List[int]) -> int:
		arr.insert(0, 1)
		arr.append(1)
		dp = [[0 for i in range(n + 2)] for j in range(n + 2)]
		for i in range(n, 0, -1):
			for j in range(1, n + 1):
				if i > j:
					continue
				maxi = float('-inf')
				for idx in range(i, j + 1):
					cost = arr[i - 1] * arr[idx] * arr[j + 1] + dp[i][idx - 1] + dp[idx + 1][j]
					maxi = max(maxi, cost)
				dp[i][j] = maxi
		return dp[1][n]


from typing import List

class Solution:

	def maxCoins(self, N: int, A: List[int]) -> int:
		dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		A = [1] + A + [1]
		dp = [[0 for x in range(N + 2)] for y in range(N + 2)]
		for length in range(1, N + 1):
			for left in range(1, N - length + 2):
				right = left + length - 1
				for last in range(left, right + 1):
					dp[left][right] = max(dp[left][right], dp[left][last - 1] + A[left - 1] * A[last] * A[right + 1] + dp[last + 1][right])
		return dp[1][N]


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		MAX_N = N + 2
		dp = [[0] * MAX_N for _ in range(MAX_N)]
		arr.insert(0, 1)
		arr.append(1)
		for length in range(0, N - 1 + 1):
			for start in range(1, N - length + 1):
				end = start + length
				max_profit = 0
				for i in range(start, end + 1):
					profit = dp[start][i - 1] + arr[start - 1] * arr[i] * arr[end + 1] + dp[i + 1][end]
					max_profit = max(max_profit, profit)
				dp[start][end] = max_profit
		return dp[1][N]


from typing import List

class Solution:

	def maxCoins(self, n: int, nums: List[int]) -> int:
		n = len(nums)
		nums = [1] + nums + [1]
		dp = [[0] * (n + 2) for _ in range(n + 2)]
		for length in range(1, n + 1):
			for i in range(1, n - length + 2):
				j = i + length - 1
				for k in range(i, j + 1):
					dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j + 1])
		return dp[1][n]


from typing import List

def fun(i, j, arr, dp):
	if i > j:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	maxi = float('-inf')
	for k in range(i, j + 1):
		maxi = max(maxi, arr[i - 1] * arr[k] * arr[j + 1] + fun(i, k - 1, arr, dp) + fun(k + 1, j, arr, dp))
	dp[i][j] = maxi
	return dp[i][j]

class Solution:

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


from typing import List
import sys

class Solution:

	def partition(self, i, j, arr, dp):
		if dp[i][j] != -1:
			return dp[i][j]
		if i > j:
			return 0
		ans = -sys.maxsize
		for k in range(i, j + 1):
			temp = arr[i - 1] * arr[j + 1] * arr[k] + self.partition(i, k - 1, arr, dp) + self.partition(k + 1, j, arr, dp)
			ans = max(ans, temp)
		dp[i][j] = ans
		return ans

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr.insert(0, 1)
		arr.append(1)
		dp = [[0 for j in range(N + 2)] for i in range(N + 2)]
		for i in range(N, 0, -1):
			for j in range(1, N + 1):
				if i > j:
					continue
				ans = -sys.maxsize
				for k in range(i, j + 1):
					temp = arr[i - 1] * arr[j + 1] * arr[k] + dp[i][k - 1] + dp[k + 1][j]
					ans = max(temp, ans)
				dp[i][j] = ans
		return dp[1][N]


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr.append(1)
		arr.insert(0, 1)
		dp = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
		for i in range(N, 0, -1):
			for j in range(1, N + 1):
				if i > j:
					continue
				maxi = -1000000000.0
				for ind in range(i, j + 1):
					cost = arr[i - 1] * arr[ind] * arr[j + 1] + dp[i][ind - 1] + dp[ind + 1][j]
					maxi = max(maxi, cost)
				dp[i][j] = maxi
		return dp[1][N]


from typing import List

class Solution:

	def tabular(self, arr):
		arr = [1] + arr + [1]
		dp = [[0 for i in range(len(arr) + 1)] for j in range(len(arr))]
		n = len(arr) - 2
		for i in range(n, 0, -1):
			for j in range(1, n + 1):
				if i <= j:
					ans = -1000000000.0
					for p in range(i, j + 1):
						coins = arr[i - 1] * arr[p] * arr[j + 1] + dp[i][p - 1] + dp[p + 1][j]
						ans = max(ans, coins)
					dp[i][j] = ans
		return dp[1][n]

	def maxCoins(self, N: int, arr: List[int]) -> int:
		return self.tabular(arr)


from typing import List

class Solution:

	def maxCoins(self, n: int, arr: List[int]) -> int:
		dp = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			i = 0
			j = g
			while j < n and i < n:
				maxx = -1000000000.0
				for k in range(i, j + 1):
					left = 0
					if i != k:
						left = dp[i][k - 1]
					right = 0
					if j != k:
						right = dp[k + 1][j]
					val = arr[k]
					if i != 0:
						val *= arr[i - 1]
					if j != n - 1:
						val *= arr[j + 1]
					total = left + right + val
					maxx = max(maxx, total)
				dp[i][j] = maxx
				i += 1
				j += 1
		return dp[0][n - 1]


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		N += 2
		A = [1] + arr + [1]
		dp = [[0] * (N + 1 - L) for L in range(N + 1)]
		for L in range(3, N + 1):
			for si in range(N - L + 1):
				dp[L][si] = max((A[si] * A[mi] * A[si + L - 1] + dp[mi - si + 1][si] + dp[si + L - mi][mi] for mi in range(si + 1, si + L - 1)))
		return dp[N][0]


from typing import List

class Solution:

	def maxCoins(self, N, arr):
		dp = [[0] * (N + 2) for _ in range(N + 2)]
		arr = [1] + arr + [1]
		for length in range(1, N + 1):
			for start in range(1, N - length + 2):
				end = start + length - 1
				for last_burst in range(start, end + 1):
					dp[start][end] = max(dp[start][end], dp[start][last_burst - 1] + dp[last_burst + 1][end] + arr[start - 1] * arr[last_burst] * arr[end + 1])
		return dp[1][N]


from typing import List

def burstBalloons(i, j, arr, dp):
	if i > j:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	maxi = 0
	for k in range(i, j + 1):
		temp = arr[i - 1] * arr[k] * arr[j + 1] + burstBalloons(i, k - 1, arr, dp) + burstBalloons(k + 1, j, arr, dp)
		maxi = max(maxi, temp)
	dp[i][j] = maxi
	return dp[i][j]

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr.insert(0, 1)
		arr.append(1)
		dp = [[-1] * (N + 1) for _ in range(N + 1)]
		return burstBalloons(1, N, arr, dp)


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		n = len(arr)
		dp = [[0 for _ in range(n)] for _ in range(n)]
		for length in range(1, n + 1):
			for i in range(n - length + 1):
				j = i + length - 1
				for k in range(i, j + 1):
					left = 1
					right = 1
					prev = 0
					forw = 0
					if i != 0:
						left = arr[i - 1]
					if j != n - 1:
						right = arr[j + 1]
					if i != k:
						prev = dp[i][k - 1]
					if j != k:
						forw = dp[k + 1][j]
					dp[i][j] = max(dp[i][j], prev + forw + left * arr[k] * right)
		return dp[0][n - 1]


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr = [1] + arr + [1]
		start = 1
		dp = [[0 for j in range(N + 2)] for i in range(N + 2)]
		while start < N + 1:
			for left in range(1, N - start + 2):
				rt = left + start - 1
				for k in range(left, rt + 1):
					dp[left][rt] = max(dp[left][rt], arr[left - 1] * arr[k] * arr[rt + 1] + dp[left][k - 1] + dp[k + 1][rt])
			start += 1
		return dp[1][N]


from typing import List

class Solution:

	def solve(self, a, l, r):
		if l > r:
			return 0
		elif l == r:
			return a[l - 1] * a[l] * a[r + 1]
		if self.mem[l][r] == -1:
			ans = 0
			for i in range(l, r + 1):
				_ans = self.solve(a, l, i - 1) + a[l - 1] * a[i] * a[r + 1] + self.solve(a, i + 1, r)
				ans = max(ans, _ans)
			self.mem[l][r] = ans
		return self.mem[l][r]

	def maxCoins(self, n: int, a: List[int]) -> int:
		a.insert(0, 1)
		a.append(1)
		dp = [[0] * (n + 2) for _ in range(n + 2)]
		for s in range(1, n + 1):
			for l in range(1, n - s + 2):
				r = l + s - 1
				for k in range(l, r + 1):
					dp[l][r] = max(dp[l][r], dp[l][k - 1] + a[l - 1] * a[k] * a[r + 1] + dp[k + 1][r])
		return dp[1][n]


from typing import List
from functools import lru_cache

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr.append(1)
		arr.insert(0, 1)
		prev_value = [[-1] * (N + 2) for _ in range(N + 2)]

		@lru_cache(None)
		def calc_balloons(left, right):
			if left > right:
				return 0
			mx = -1000000000.0
			ans = 0
			for i in range(left, right + 1):
				ans = calc_balloons(left, i - 1) + calc_balloons(i + 1, right) + arr[left - 1] * arr[i] * arr[right + 1]
				mx = max(mx, ans)
			return mx
		return calc_balloons(1, N)


from typing import List

class Solution:

	@staticmethod
	def maxCoins(N: int, arr: List[int]) -> int:
		mat_size = N + 2
		res_mat = [[0] * mat_size for _ in range(mat_size)]
		arr = [1] + arr + [1]
		length = 1
		while length <= N:
			for left in range(1, mat_size - length):
				right = left + length - 1
				for last_burst in range(left, right + 1):
					coins = arr[left - 1] * arr[last_burst] * arr[right + 1]
					coins += res_mat[left][last_burst - 1] + res_mat[last_burst + 1][right]
					if res_mat[left][right] < coins:
						res_mat[left][right] = coins
			length += 1
		return max(max(res_mat))


from functools import lru_cache
from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr = [1] + arr + [1]

		@lru_cache(maxsize=None)
		def dfs(l, r):
			if l > r:
				return 0
			t = 0
			for i in range(l, r + 1):
				t = max(t, dfs(l, i - 1) + dfs(i + 1, r) + arr[l - 1] * arr[i] * arr[r + 1])
			return t
		return dfs(1, N)


from typing import List
import copy

class Solution:

	def dp(self, i: int, j: int, left: int, right: int, nums: List[List[int]], arr: List[int]):
		if nums[i][j] != -1:
			return nums[i][j]
		res = 0
		for k in range(i, j):
			gain = left * arr[k] * right
			gain += self.dp(i, k, left, arr[k], nums, arr) + self.dp(k + 1, j, arr[k], right, nums, arr)
			res = max(gain, res)
		nums[i][j] = res
		return res

	def maxCoins(self, N: int, arr: List[int]) -> int:
		nums = [[-1 for i in range(N + 1)] for j in range(N + 1)]
		return self.dp(0, N, 1, 1, nums, arr)


from typing import List

class Solution:

	def maxCoins(self, l_n: int, nums: List[int]) -> int:
		nums = [1] + nums + [1]
		dp = [[-1 for i in range(l_n + 1)] for j in range(l_n + 1)]

		def dfs(l, r):
			if l > r:
				return 0
			if dp[l][r] != -1:
				return dp[l][r]
			dp[l][r] = 0
			maxi = float('-inf')
			for i in range(l, r + 1):
				coins = nums[l - 1] * nums[i] * nums[r + 1]
				coins += dfs(l, i - 1) + dfs(i + 1, r)
				if coins > maxi:
					maxi = coins
				dp[l][r] = maxi
			return dp[l][r]
		return dfs(1, len(nums) - 2)


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		import sys
		arr.append(1)
		arr.insert(0, 1)
		array = [[0 for i in range(N + 2)] for j in range(N + 2)]
		for i in range(N, 0, -1):
			for j in range(1, N + 1):
				maxCoins = -sys.maxsize - 1
				for k in range(i, j + 1):
					coins = arr[i - 1] * arr[k] * arr[j + 1] + array[i][k - 1] + array[k + 1][j]
					if coins > maxCoins:
						maxCoins = coins
					array[i][j] = maxCoins
		return array[1][N]


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr = [1] + arr[:] + [1]
		dp = [[-1 for i in range(N + 1)] for j in range(N + 1)]

		def maxCoinsUtil(i, j, dp):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			maxi = float('-inf')
			for index in range(i, j + 1):
				cost = arr[i - 1] * arr[index] * arr[j + 1] + maxCoinsUtil(i, index - 1, dp) + maxCoinsUtil(index + 1, j, dp)
				maxi = max(maxi, cost)
			dp[i][j] = maxi
			return maxi
		return maxCoinsUtil(1, N, dp)


from typing import List
import copy

class Solution:

	def maxCoins(self, N: int, nums: List[int]) -> int:
		if len(nums) > 1 and len(set(nums)) == 1:
			return nums[0] ** 3 * (len(nums) - 2) + nums[0] ** 2 + nums[0]
		nums = [1] + nums + [1]
		n = len(nums)
		dp = [[0] * n for _ in range(n)]
		for left in range(n - 2, 0, -1):
			for right in range(left, n - 1):
				for i in range(left, right + 1):
					gain = nums[left - 1] * nums[i] * nums[right + 1]
					remaining = dp[left][i - 1] + dp[i + 1][right]
					dp[left][right] = max(remaining + gain, dp[left][right])
		return dp[1][n - 2]


from typing import List

class Solution:

	def maxCoins(self, N: int, arr: List[int]) -> int:
		arr.append(1)
		arr.insert(0, 1)
		val = [[0 for j in arr] for i in arr]
		for j in range(1, N + 1):
			val[j][j] = arr[j] * arr[j - 1] * arr[j + 1]
		for i in range(1, N):
			for j in range(1, N + 1 - i):
				for k in range(j, i + j + 1):
					val[j][i + j] = max(val[j][i + j], arr[j - 1] * arr[i + j + 1] * arr[k] + val[j][k - 1] + val[k + 1][i + j])
		return val[1][N]


from typing import List

class Solution:

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

		def val(prev, curr, nxt):
			value = arr[curr]
			if prev > -1:
				value *= arr[prev]
			if nxt < N:
				value *= arr[nxt]
			return value
		dp = [[0 for i in range(N)] for i in range(N)]
		for i in range(N):
			dp[i][i] = val(i - 1, i, i + 1)
		for x in range(1, N):
			i = 0
			for j in range(x, N):
				final = 0
				for k in range(i, j + 1):
					value = 0
					if k - 1 > -1:
						value += dp[i][k - 1]
					if k + 1 < N:
						value += dp[k + 1][j]
					value += val(i - 1, k, j + 1)
					final = max(value, final)
				dp[i][j] = final
				i += 1
		return dp[0][-1]


from typing import List
from functools import lru_cache

class Solution:

	def maxCoins(self, N: int, nums: List[int]) -> int:
		nums.append(1)
		nums.insert(0, 1)

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