Balloon burst problem leetcode

#1

i want to solve this problem using the matrix chain multiplication technique…
provide the code for it along with explaination…

#2

hello @S19LPPP0202

dp[i][j] in here means, the maximum coins we get after we burst all the balloons between i and j in the original array.

For example with input [3,1,5,8] :

dp[0][0] means we burst ballons between [0,0], which means we only burst the first balloon in original array. So dp[0][0] is 1 * 3 * 1 = 3.

dp[1][1] means we burst balloons between [1][1], which means we only burst the second ballon in the original array. So dp[1][1] is 3 * 1 * 5 = 15.

So in the end for this problem we want to find out dp[0][ arr.length - 1 ], which is the maximum value we can get when we burst all the balloon between [0 , length -1]

To get that we need the transition function :

for (int k = left; k <= right; ++k)
dp[left][right] = max(dp[left][right], nums[left-1] * nums[k] * nums[right+1] + dp[left][k-1] + dp[k+1][right]) **

This transition function basically says in order to get the maximum value we can get for bursting all the balloons between [ i , j] , we just loop through each balloon between these two indexes and make them to be the last balloon to be burst,

why we pick it as the last balloon to burst ?

For example when calculating dp[0,3] and picking index 2 as the last balloon to burst,

[ 3 , 1 , 5 , 8] , that means 5 is the last balloon to burst between [0,3] , to get the maximum value when picking 5 as the last balloon to burst :

max = maximum value of bursting all the balloon on the left side of 5 + maximum value of bursting all the balloon on the right side of 5 + bursting balloon 5 when left side and right side are gone.

That is dp[0, 1] + nums[0 - 1] * nums[2] * nums[3 + 1] + + dp[3,3];

That is dp[left, k - 1] + nums[left - 1] * nums[k] * nums[right + 1] + dp[k+1, right] ;

to get the maximum dp[left, right] we just loop through all the possible value of k to get the maximum.

still not clear?
refer this -> GUBBARA

Right now i dont have code for it, you try to code it . if u stuck then tell me ,i will code it and share it with u,

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.