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.

Leetcode Burst Balloons problem solution

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];
     
    }
};

coding problems