We have been given N balloons, each with a number of coins associated with it. On bursting a balloon i, the number of coins gained is equal to A[i-1]*A[i]*A[i+1].
Also, balloons i-1 and i+1 now become adjacent. Find the maximum possible profit earned after bursting all the balloons. Assume an extra 1 at each boundary.
Example 1:
Input: 
N=2
a[]={5, 10}
Output: 
60
Explanation: First Burst 5, Coins = 1*5*10
              Then burst 10, Coins+= 1*10*1
              Total = 60
Example 2:
Input:
N=4
a[] = {3,1,5,8}
Output:
167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxCoins() which takes the array arr[], its size N, and returns the maximum number of coins that can be collected.
Expected Time Complexity: O(N^3)
Expected Space Complexity: O(N^2)
Constraints:
1 <= N <= 400
0 <= a[i] <= 100

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution():

    def maxCoins(self, N, a):

        #your code goes here

Solutions:
class Solution:

	def maxCoins(self, N, a):
		dp = [[0] * N for _ in range(N)]
		for left in range(N, -1, -1):
			for right in range(left, N):
				for k in range(left, right + 1):
					v = a[k]
					if left - 1 >= 0:
						v *= a[left - 1]
					if right + 1 < N:
						v *= a[right + 1]
					if left <= k - 1:
						v += dp[left][k - 1]
					if k + 1 <= right:
						v += dp[k + 1][right]
					dp[left][right] = max(dp[left][right], v)
		return dp[0][N - 1]


class Solution:
	dp = []

	def gen(self, i, j, a):
		if i > j:
			return 0
		if self.dp[i][j] != -1:
			return self.dp[i][j]
		maxi = -9
		for k in range(i, j + 1):
			ans = a[i - 1] * a[k] * a[j + 1] + self.gen(i, k - 1, a) + self.gen(k + 1, j, a)
			maxi = max(maxi, ans)
		self.dp[i][j] = maxi
		return maxi

	def maxCoins(self, n, a):
		self.dp = []
		for i in range(n + 2):
			arr = []
			for j in range(n + 2):
				arr.append(0)
			self.dp.append(arr)
		a.insert(0, 1)
		a.append(1)
		for i in range(n, 0, -1):
			for j in range(1, n + 1):
				if i > j:
					continue
				maxi = -9
				for k in range(i, j + 1):
					ans = a[i - 1] * a[k] * a[j + 1] + self.dp[i][k - 1] + self.dp[k + 1][j]
					maxi = max(maxi, ans)
				self.dp[i][j] = maxi
		return self.dp[1][n]


class Solution:

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


class Solution:

	def maxCoins(self, N, A):
		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]


class Solution:

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


from functools import lru_cache

class Solution:

	def maxCoins(self, N, seq):
		tabres = [[-1 for bla in range(N + 1)] for blabla in range(N + 1)]
		for gap in range(1, N + 1):
			for i in range(N - gap + 1):
				j = i + gap
				res = float('-inf')
				for k in range(i, j):
					neiA = seq[i - 1] if i - 1 >= 0 else 1
					neiB = seq[j] if j < len(seq) else 1
					left = tabres[i][k] if tabres[i][k] != -1 else 0
					right = tabres[k + 1][j] if tabres[k + 1][j] != -1 else 0
					res = max(res, left + right + seq[k] * neiA * neiB)
				tabres[i][j] = res
		return res


class Solution:

	def maxCoins(self, N, cuts):
		cuts.append(1)
		cuts.insert(0, 1)
		dp = [[0] * (N + 2) for x in range(N + 2)]
		for i in range(N, 0, -1):
			for j in range(1, N + 1):
				maxi = 0
				for ind in range(i, j + 1):
					cost = cuts[j + 1] * cuts[ind] * cuts[i - 1] + dp[i][ind - 1] + dp[ind + 1][j]
					maxi = max(maxi, cost)
				dp[i][j] = maxi
		return dp[1][N]


class Solution:

	def maxCoins(self, N, a):
		memory = [[0 for i in range(N)] for i in range(N)]
		for lb in range(N, -1, -1):
			for ub in range(lb, N):
				for ce in range(lb, ub + 1):
					local = a[ce]
					if lb > 0:
						local *= a[lb - 1]
					if ub < N - 1:
						local *= a[ub + 1]
					if lb < ce:
						local += memory[lb][ce - 1]
					if ub > ce:
						local += memory[ce + 1][ub]
					memory[lb][ub] = max(memory[lb][ub], local)
		return memory[0][N - 1]


class Solution:

	def maxCoins(self, N, arr):
		A = [1] + arr + [1]
		dp = [[0 for j in range(n + 2)] for i in range(n + 2)]
		for l in range(1, n + 1):
			for i in range(1, n - l + 2):
				j = i + l - 1
				for k in range(i, j + 1):
					dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + A[i - 1] * A[k] * A[j + 1])
		return dp[1][n]


class Solution:

	def maxCoins(self, N, a):
		a = [1] + a + [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] + a[i - 1] * a[k] * a[j + 1])
		return dp[1][N]


class Solution:

	def maxCoins(self, n, arr):
		arr = [1] + arr + [1]
		dp = [[0] * (n + 2) for i 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] + arr[i - 1] * arr[k] * arr[j + 1])
		return dp[1][n]


class Solution:

	def maxCoins(self, N, a):
		dp = [[0 for i in range(N + 2)] for j in range(N + 2)]
		a.insert(0, 1)
		a.append(1)
		for i in range(0, N - 1 + 1):
			for start in range(1, N - i + 1):
				end = start + i
				res = 0
				for k in range(start, end + 1):
					temp = dp[start][k - 1] + a[start - 1] * a[k] * a[end + 1] + dp[k + 1][end]
					res = max(res, temp)
				dp[start][end] = res
		return dp[1][N]


class Solution:

	def maxCoins(self, N, a):
		n = len(a)
		a = [1] + a + [1]
		dp = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
		for length in range(1, n + 1):
			for left in range(1, n - length + 2):
				right = left + length - 1
				for k in range(left, right + 1):
					dp[left][right] = max(dp[left][right], a[left - 1] * a[k] * a[right + 1] + dp[left][k - 1] + dp[k + 1][right])
		return dp[1][n]


class Solution:

	def maxCoins(self, N, a):
		N = len(a)
		a = [1] + a + [1]
		dp = [[0] * (N + 2) for _ in range(N + 2)]
		for gap in range(N + 1):
			for i in range(1, N + gap + 1):
				j = i + gap
				if j <= N:
					for k in range(i, j + 1):
						dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + a[i - 1] * a[k] * a[j + 1])
		return dp[1][N]


class Solution:

	def maxCoins(self, N, a):
		MAX_N = N + 2
		dp = [[0] * MAX_N for _ in range(MAX_N)]
		a.insert(0, 1)
		a.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] + a[start - 1] * a[i] * a[end + 1] + dp[i + 1][end]
					max_profit = max(max_profit, profit)
				dp[start][end] = max_profit
		return dp[1][N]


from functools import lru_cache

class Solution:

	def maxCoins(self, n, arr):
		arr = [1] + arr + [1]
		n += 2

		@lru_cache(None)
		def helper(l, r):
			if r - l < 2:
				return 0
			ans = 0
			for i in range(l + 1, r):
				ans = max(ans, arr[l] * arr[i] * arr[r] + helper(l, i) + helper(i, r))
			return ans
		return helper(0, n - 1)


class Solution:

	def help(self, dp, a, N, start, end):
		if start > end:
			return 0
		if dp[start][end] != -1:
			return dp[start][end]
		temp = 1
		if start != 0:
			temp *= a[start - 1]
		if end != N - 1:
			temp *= a[end + 1]
		for i in range(start, end + 1):
			t = temp * a[i]
			dp[start][end] = max(dp[start][end], t + self.help(dp, a, N, i + 1, end) + self.help(dp, a, N, start, i - 1))
		return dp[start][end]

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


class Solution:

	def maxCoins(self, n, a):
		dp = [[0] * n for _ in range(n)]
		for gap in range(n):
			(i, j) = (0, gap)
			while j < n:
				for k in range(i, j + 1):
					l = 0 if k == i else dp[i][k - 1]
					r = 0 if k == j else dp[k + 1][j]
					m = a[k]
					if i > 0:
						m *= a[i - 1]
					if j < n - 1:
						m *= a[j + 1]
					dp[i][j] = max(dp[i][j], l + m + r)
				i += 1
				j += 1
		return dp[0][n - 1]


class Solution:

	def maxCoins(self, N, A):
		A = [1] + A + [1]
		n = len(A)
		dp = [[0] * n for _ in range(n)]
		for length in range(2, n):
			for left in range(0, n - length):
				right = left + length
				for i in range(left + 1, right):
					dp[left][right] = max(dp[left][right], A[left] * A[i] * A[right] + dp[left][i] + dp[i][right])
		return dp[0][n - 1]


class Solution:

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

	def maxCoins(self, N, a):
		n = len(a)
		a.insert(0, 1)
		a.insert(len(a), 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
				maxi = float('-inf')
				for last in range(i, j + 1):
					cost = a[i - 1] * a[last] * a[j + 1] + dp[i][last - 1] + dp[last + 1][j]
					maxi = max(maxi, cost)
				dp[i][j] = maxi
		return dp[1][n]


class Solution:

	def maxCoins(self, N, a):
		nj = [[0] * N for _ in range(N)]
		for left in range(N, -1, -1):
			for right in range(left, N):
				for k in range(left, right + 1):
					ll = a[k]
					if left - 1 >= 0:
						ll *= a[left - 1]
					if right + 1 < N:
						ll *= a[right + 1]
					if left <= k - 1:
						ll += nj[left][k - 1]
					if k + 1 <= right:
						ll += nj[k + 1][right]
					nj[left][right] = max(nj[left][right], ll)
		return nj[0][N - 1]


class Solution:

	def maxCoins(self, N, a):
		x = [[0] * N for _ in range(N)]
		for left in range(N, -1, -1):
			for right in range(left, N):
				for k in range(left, right + 1):
					r = a[k]
					if left - 1 >= 0:
						r *= a[left - 1]
					if right + 1 < N:
						r *= a[right + 1]
					if left <= k - 1:
						r += x[left][k - 1]
					if k + 1 <= right:
						r += x[k + 1][right]
					x[left][right] = max(x[left][right], r)
		return x[0][N - 1]


import math

class Solution:

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

def subproblem(l, r, N, a, dp):
	if l > r:
		return 0
	if dp[l][r] != -1:
		return dp[l][r]
	maxVal = -math.inf
	for k in range(l, r + 1):
		leftVal = 1 if l <= 0 else a[l - 1]
		rightVal = 1 if r >= N - 1 else a[r + 1]
		maxVal = max(maxVal, subproblem(l, k - 1, N, a, dp) + subproblem(k + 1, r, N, a, dp) + a[k] * leftVal * rightVal)
	dp[l][r] = maxVal
	return dp[l][r]

class Solution1:

	def maxCoins(self, N, a):
		dp = [[-1 for j in range(N)] for i in range(N)]
		return subproblem(0, N - 1, N, a, dp)


class Solution:

	def maxCoins(self, N, a):

		def solve(l, r):
			if l > r:
				return 0
			ans = -1000000
			if dp[l][r] != -1:
				return dp[l][r]
			for k in range(l, r + 1):
				ans = max(ans, solve(l, k - 1) + solve(k + 1, r) + a[k] * (a[l - 1] if l - 1 >= 0 else 1) * (a[r + 1] if r + 1 < len(a) else 1))
			dp[l][r] = ans
			return ans
		dp = [[-1] * N for _ in range(N)]
		for l in range(N, -1, -1):
			for r in range(l, N):
				for k in range(l, r + 1):
					s = a[k]
					if l - 1 >= 0:
						s *= a[l - 1]
					if r + 1 < N:
						s *= a[r + 1]
					if l <= k - 1:
						s += dp[l][k - 1]
					if k + 1 <= r:
						s += dp[k + 1][r]
					dp[l][r] = max(dp[l][r], s)
		return dp[0][N - 1]


class Solution:

	def maxCoins(self, N, a):
		nums = [1] + [i for i in a if i > 0] + [1]
		n = len(nums)
		dp = [[0] * n for _ in range(n)]
		for k in range(2, n):
			for left in range(0, n - k):
				right = left + k
				for i in range(left + 1, right):
					dp[left][right] = max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right])
		return dp[0][n - 1]


class Solution:

	def maxCoins(self, N, a):
		dp = [[0] * N for i in range(N)]
		for i in range(N, -1, -1):
			for j in range(i, N):
				for k in range(i, j + 1):
					c = a[k]
					if i - 1 >= 0:
						c *= a[i - 1]
					if j + 1 < N:
						c *= a[j + 1]
					if i <= k - 1:
						c += dp[i][k - 1]
					if k + 1 <= j:
						c += dp[k + 1][j]
					dp[i][j] = max(dp[i][j], c)
		return dp[0][N - 1]


class Solution:

	def maxCoins(self, n, nums):
		nums.append(1)
		nums.insert(0, 1)
		dp = [[0] * len(nums) for _ in range(len(nums))]
		for i in range(len(nums) - 1, 0, -1):
			for j in range(i, len(nums) - 1):
				maxi = 0
				for k in range(i, j + 1):
					points = nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]
					maxi = max(maxi, points)
				dp[i][j] = maxi
		return dp[1][len(nums) - 2]


from functools import lru_cache

class Solution:

	def maxCoins(self, N, a):
		a = [1] + a + [1]

		@lru_cache(maxsize=None)
		def recur(l, r):
			res = 0
			for i in range(l + 1, r):
				res = max(res, a[l] * a[i] * a[r] + recur(l, i) + recur(i, r))
			return res
		return recur(0, N + 1)


class Solution:

	def maxCoins(self, N, a):
		A = a
		A = [1] + A + [1]
		memo = [[None] * (N + 2) for i in range(N + 2)]

		def dp(i, j):
			if memo[i][j] is not None:
				return memo[i][j]
			if i > j:
				return 0
			if i == j:
				return A[i - 1] * A[i] * A[i + 1]
			ans = 0
			for k in range(i, j + 1):
				ans = max(ans, dp(i, k - 1) + dp(k + 1, j) + A[i - 1] * A[k] * A[j + 1])
			memo[i][j] = ans
			return ans
		return dp(1, N)


class Solution:

	def maxCoins(self, N, a):
		l = [1]
		for i in range(N):
			l.append(a[i])
		l.append(1)
		length = N + 2
		sum = [[0 for i in range(length)] for j in range(length)]
		for i in range(length - 3, -1, -1):
			for j in range(i + 2, length):
				for p in range(i + 1, j):
					sum[i][j] = max(sum[i][j], sum[i][p] + sum[p][j] + l[i] * l[p] * l[j])
		return sum[0][length - 1]


class Solution:

	def maxCoins(self, N, a):
		dp = [[0] * N for _ in range(N)]
		for low in range(N, -1, -1):
			for high in range(low, N):
				for k in range(low, high + 1):
					h = a[k]
					if low - 1 >= 0:
						h *= a[low - 1]
					if high + 1 < N:
						h *= a[high + 1]
					if low <= k - 1:
						h += dp[low][k - 1]
					if k + 1 <= high:
						h += dp[k + 1][high]
					dp[low][high] = max(dp[low][high], h)
		return dp[0][N - 1]


class Solution:

	def maxCoins(self, N, a):
		A = [[0] * N for _ in range(N)]
		for AA in range(N, -1, -1):
			for AAA in range(AA, N):
				for k in range(AA, AAA + 1):
					v = a[k]
					if AA - 1 >= 0:
						v *= a[AA - 1]
					if AAA + 1 < N:
						v *= a[AAA + 1]
					if AA <= k - 1:
						v += A[AA][k - 1]
					if k + 1 <= AAA:
						v += A[k + 1][AAA]
					A[AA][AAA] = max(A[AA][AAA], v)
		return A[0][N - 1]


class Solution:

	def maxCoins(self, N, a):
		a = [1] + a + [1]
		N += 2
		dp = [[0 for i in range(N)] for j in range(N)]
		for l in range(3, N + 1):
			for i in range(N - l + 1):
				j = i + l - 1
				for k in range(i + 1, j):
					dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
		return dp[0][N - 1]


from typing import List

class Solution:

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