## Algorithm

Problem Name: 312. Burst Balloons

You are given `n` balloons, indexed from `0` to `n - 1`. Each balloon is painted with a number on it represented by an array `nums`. You are asked to burst all the balloons.

If you burst the `ith` balloon, you will get `nums[i - 1] * nums[i] * nums[i + 1]` coins. If `i - 1` or `i + 1` goes out of bounds of the array, then treat 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: nums = [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```

Example 2:

```Input: nums = [1,5]
Output: 10
```

Constraints:

• `n == nums.length`
• `1 <= n <= 300`
• `0 <= nums[i] <= 100`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
function maxCoins(arr) {
const len = arr.length
const nums = Array(len + 2).fill(0);
let n = 1;
for (const x of arr) if (x > 0) nums[n++] = x;
nums[0] = nums[n++] = 1;

const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let k = 2; k  <  n; k++) {
for (let left = 0; left  <  n - k; left++) {
let right = left + k;
for (let i = left + 1; i  <  right; i++) {
dp[left][right] = Math.max(
dp[left][right],
nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right],
);
}
}
}

return dp[0][n - 1];
}
``````
Copy The Code &

Input

cmd
nums = [3,1,5,8]

Output

cmd
167

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxCoins(self, nums):
memo, nums = {}, [1] + [num for num in nums if num] + [1]
def dfs(l, r):
if r - l == 1: return 0
if (l, r) not in memo: memo[(l, r)] = max(nums[l] * nums[i] * nums[r] + dfs(l, i) + dfs(i, r) for i in range(l + 1, r))
return memo[(l, r)]
return dfs(0, len(nums) - 1)
``````
Copy The Code &

Input

cmd
nums = [3,1,5,8]

Output

cmd
167

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0312_BurstBalloons
{
public int MaxCoins(int[] nums)
{
var paddingNums = new int[nums.Length + 2];
for (int i = 0; i  <  nums.Length; i++)

}

private int DP(int[] nums, int left, int right, int[,] memo)
{
if (right - left == 1) return 0;
if (memo[left, right] > 0) return memo[left, right];

var result = 0;
for (int i = left + 1; i  <  right; i++)
result = Math.Max(
result,
nums[left] * nums[i] * nums[right] + DP(nums, left, i, memo) + DP(nums, i, right, memo)
);

memo[left, right] = result;
return result;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,5]

Output

cmd
10