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.length1 <= n <= 3000 <= 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];
}
Input
Output
#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)
Input
Output
#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++)
paddingNums[i + 1] = nums[i];
paddingNums[0] = paddingNums[nums.Length + 1] = 1;
var memo = new int[paddingNums.Length, paddingNums.Length];
return DP(paddingNums, 0, paddingNums.Length - 1, memo);
}
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;
}
}
}
Input
Output