Here, We see Burst Balloons LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Burst Balloons LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Burst Balloons LeetCode Solution
Table of Contents
Problem Statement
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
Burst Balloons LeetCode Solution C++
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size() + 2;
vector<vector<int>> dp(n, vector<int>(n));
vector<int> new_nums(n, 1);
int i = 1;
for(auto num : nums) {
new_nums[i++] = num;
}
for(int len = 2; len <= n; len++) {
for(int i = 0; i <= n - len; i++) {
int j = i + len - 1;
for(int k = i + 1; k < j; k++) {
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + new_nums[i] * new_nums[k] * new_nums[j]);
}
}
}
return dp[0][n - 1];
}
};
Code language: PHP (php)
Burst Balloons LeetCode Solution Java
class Solution {
public int maxCoins(int[] nums) {
int[] inums = new int[nums.length + 2];
int n = 1;
for (int x : nums) if (x > 0) inums[n++] = x;
inums[0] = inums[n++] = 1;
int[][] memo = new int[n][n];
return burst(memo, inums, 0, n - 1);
}
public int burst(int[][] memo, int[] inums, int left, int right) {
if (left + 1 == right) return 0;
if (memo[left][right] > 0) return memo[left][right];
int ans = 0;
for (int i = left + 1; i < right; ++i)
ans = Math.max(ans, inums[left] * inums[i] * inums[right] + burst(memo, inums, left, i) + burst(memo, inums, i, right));
memo[left][right] = ans;
return ans;
}
}
Code language: PHP (php)
Burst Balloons Solution JavaScript
var maxCoins = function(nums) {
var auxArray = new Array(nums.length+2).fill(null);
let idx = 1;
for (let numsVal of nums){
if(numsVal > 0) auxArray[idx++] = numsVal;
}
auxArray[0] = auxArray[idx++] = 1;
var cache = Array.from({length: idx}, ()=>new Array(idx).fill([]));
return burst(cache, auxArray, 0, idx - 1);
}
function burst(cache, auxArray, left, right) {
if (left + 1 == right) return 0;
if (cache[left][right] > 0) return cache[left][right];
let max = 0;
for (let idx = left + 1; idx < right; idx++)
max = Math.max(max, auxArray[left] * auxArray[idx] * auxArray[right] + burst(cache, auxArray, left, idx) + burst(cache, auxArray, idx, right));
cache[left][right] = max;
return max;
}
Code language: JavaScript (javascript)
Burst Balloons Solution Python
class Solution(object):
def maxCoins(self, nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in xrange(n)]
def calculate(i, j):
if dp[i][j] or j == i + 1: # in memory or gap < 2
return dp[i][j]
coins = 0
for k in xrange(i+1, j): # find the last balloon
coins = max(coins, nums[i] * nums[k] * nums[j] + calculate(i, k) + calculate(k, j))
dp[i][j] = coins
return coins
return calculate(0, n-1)
Code language: HTML, XML (xml)