# Leetcode Burst Balloons problem solution

In this Leetcode Burst Balloons problem solution 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.

## Problem solution in Python.

```class Solution:
def maxCoins(self, nums: List[int]) -> int:
if not nums: return 0
nums = [1]+nums+[1]
@functools.lru_cache(None)
def foo(i,j):
if j-i<=1:  return 0
return max(nums[i]*nums[k]*nums[j] + foo(i,k) + foo(k,j) for k in range(i+1,j))
return foo(0,len(nums)-1)
```

## Problem solution in Java.

```class Solution {

public int maxCoins(int[] nums) {
int[] num = new int[nums.length+2];
num[0] = 1;
num[num.length-1] = 1;
int i = 1;
for(int val : nums)
{
num[i] = val;
i++;
}
int L = 0;
int R = num.length-1;
return burstballoon(num , L , R , new int[num.length][num.length]);
}
public int burstballoon(int[] num , int l , int r , int[][] dp)
{
if(l == r-1)
return 0;
int ans = 0;
if(dp[l][r]!=0)
return dp[l][r];
for(int i = l + 1 ; i < r ; i++)
{
int left = burstballoon(num, l, i , dp);
int right = burstballoon(num, i, r, dp);
// int curr = num[i];
ans = Math.max(ans , left + right + (num[i]*num[l]*num[r]));
}
dp[l][r] = ans;
return ans;
}
}
```

## Problem solution in C++.

```class Solution {
public:

int maxCoins(vector<int>& nums) {
nums.push_back(1);
nums.insert(nums.begin(),1,1);
int n = nums.size();
vector<vector<int>> dp(n+2,vector<int>(n+2,0));
int i = 0,j = 0,k =2;
for(int gap = 2;gap<n;gap++){
for(int l = 0; l<=n-gap-1;l++){
int r = l+gap;
for(int i = l+1;i<r;i++)
dp[l][r] = max(dp[l][r], dp[l][i]+dp[i][r]+nums[i]*nums[l]*nums[r]);
}
}
return dp[0][n-1];

}
};
```