Burst Balloon Dynamic Programming[Leetcode]

hello friends my name is Tushar and today I am going to talk about the question bursting balloons to maximize value this is a question from leet code so let me explain you the question you're given an array of positive numbers representing the value of that balloons you have to find the order in which to burst the balloons so that you can maximize the value let me help let me explain that with an example let's say I busted the balloon in order 1 3 5 8 so the first balloon I burst is 1 so when you burst a balloon the math the value you get is the multiplication of the left neighbor of this guy right neighbor of this guy and this guy so the value I get here is 1 into 3 into 5 then what is bursted so one is gone so the next balloon to burst is three so three does it have a left neighbor so we take a value of 1 for that into 3 and now the right neighbor of 3 is 5 because 1 is so 5 plus so not freeze bursted so the next button Traverse is 5 so 5 doesn't have a left neighbor so 1 into 5 and then the right number is 8 and now 5 is bursted and then the last balloon to verse is 8 so 1 into 8 into 1 so the total value you get here is 15 plus 15 plus 40 plus 8 and this value is 78 let's look at another order to burst the balloon so this is the first order another order could be 5 1 3 8 so let's write this again so now I am going to burst the balloon in this order so the first button vs. 5 so those are the value I get is 5 in through left neighbor of 5 1 and then right number of 5 which is 8 and now fly this burst rate so the next balloon burst is 1 so left favor of one is three into one into right Deborah one is eight and then the next value 2 versus 3 so 1 into 3 into 8 and then the last value 2 versus 8 so 1 into 8 into 1 so the total value in this case is 40 plus 24 plus 24 plus 8 so this number is for the a plus 4 896 so as you can see if a burst balloon in this order I get 96 value if I get burst balloon in this order then I get 78 well you so the idea is to find the order image to burst the balloon so that we can maximize this value next let's see how we solve this question we are going to use bottom of dynamic programming to solve this question so the idea is to get every sub array of every length of this array and for every separate find the last balloon which needs to burst to maximize the value for that sub array once we have calculated that for every separate we can use that information to find the maximum value we can get for that and time array so first we do is we take a two-dimensional array the number of rows and number of columns in this array is going to be same as the size of size of our original array and in here we are going to fill up the value in this diagonal 4 and at the top right corner we'll have our answer every square in this result matrix is capable of holding two values first is what is the maximum value we can get for a sub array and second is what is the last balloon that needs to burst in that separate so next let's work through this example let initially is 1 which means that we are looking at every sub array of length 1 so the first sub array of length 1 starts from 0 and ends at 0 which is why we are going to fill up this call this particular square 0 0 starts at the 0 and ends at this 0 so if I was only considering 3 only considering this one element 3 and if this was the last balloon to burst in this the value I will get is there is nothing on the there's nothing on the left of 3 so 0 plus there is nothing on the right of 3 because our summary is just restricted to one one element zero plus when this balloon bursts the value I get is 1 into 3 into this value 1 so the total value here is 3 so if 3 was the last balloon if if this 3 was last balloon to burst in this group of in this array of length 1 will get a value 3 and we'll also note that the index 0 or the balloon at index 0 is the last balloon to burst our length is still 1 and now we are looking at this element at index 1 so again when we are saying 1 which means that starts at 1 and that's 1 which is why we were to fill up this value 1 1 which is the square so again here since 1 is the only balloon and it's a last village burst from the left side it gets nothing because we are considering a sub array of only of length 1 so 0 from the right side it gets nothing plus if one burst the total value to be get is 3 into 1 into 5 so the total is 15 so 15 is the tote is a maximum value I can get in this sub array of length 1 and we'll also note the index of the balloon it should burn bush the last in that group our length is still 1 and now we are going to look at this guy again starting at to any a 2 so we're going to fit up the square so again if 5 is the last tuber so 0 we don't get anything from the left we don't get anything from the right and then 1 into 5 into 8 so the total value is 40 and we are going to note that 2 is the last index balloon at index 2 is the last one to burst and finally 3 3 starting at 3 and three the value I can get is zero plus zero plus a 5 into 8 into 1 so this is 40 again so this is how we filled up zero this is how we filled up our array subarray for length 1 next we are going to work on a sub array of length 2 so when I say sorry off lens - we can drink all the sub arrays of length 2 so first one starts at 0 and ends at 1 so our eye is 0 J is 1 and now they're going to try every possible values of K and see between I and J and see which should be the last balloon to burst so initially our k will be a value I so if value I or if 0 is the last balloon to burst the torque value I get is if 0 is the last-minute reverse the total area I get is there is nothing on the left so 0 + if if this sub array if this balloon bursts the total value we get here is 1 1 which we already calculated so 50 plus this will be the last balloon to burst in this sub array so one from the left 3 and now remember this one is gone because this is the last volume to burst in this array so you multiply this 3 with this 5 and the total value here is 30 so if 0 is the if 0 is the first last balloon to burst in this array of length 2 then we get a value of 30 let's try 1 if the balloon at index 1 is the last button to burst then from the left side we get a value of so the left side is 0 at 0 so we get a value of 3 also from laughing at a value of 3 from the right you get no value because this is the right most end of this abrasive 0 plus if this is the last balloon to burst which means that 3 is already busted so we're going to multiply whatever is on the left of 3 which is basically we take 1 and then so on and then this five so the total value we get here is it so 30 is greater than eight which means that we are going to say that the maximum value I can expect to get in this array is thirty and I would like to burst my zero to balloon as a last balloon in this sub array next we are going to consider sub array of length two starting at I 1 and ending at J 2 so here we are going to fill up this value starting at I 1 and J 2 so we are going to fill up the square so again if one is the last balloon to burst so if ki bijlee is I so why if one is the last balloon to burst so from the left side we get no values of zero one is the last value diverse from the right side I voted to two so since this is we are looking that in this sub array except this guy words the value I can get that is 2 2 so we go to to to selects values for T plus if this is the last value to burst so the value I get here is 3 into 1 into 5 is gone so 8 so the total value here is 24 plus 40 64 next our K becomes ki increments and K becomes J so 2 is the last one to burst the 3 set 2 is the last value to burst the total value can expect to get is from the left side 1 1 I can get 15 from the right side I get nothing and by bursting this guy last two regular can get is 3 because remember one is already busted so 3 into 5 into 8 so this value is 135 40 120 + 15 135 so we would this value is obviously greater than 64 so we would like this the worst I will like this balloon to divorce last in this growth so one two two and two should be the last balloon to burst so let's look at the last group of let two which starts from two and start from 2 and enter J so 2 3 start from 23 so 2 3 so if 2 is the last balloon to burst the value I can expect to get is 0 from the left side 3 3 has a value 44 40 from the right side plus 1 into 5 into 1 because this 8 is gone so 1 into 5 into whatever is on the right of it there is nothing so we take a value 1 so this is this is 40 plus 5 45 if 3 is the last balloon to burst in this group of 2 3 the value I can expect to get is from the left of 8 so 2 2 so 2 2 gives me a value of 40 plus right of it we get nothing 0 and then it is the last to verse 5 is already gone so we multiply one with 8 with one so this values for it so bursting 48 is greater than 45 so we take we make the burst three as a last in this group so the value here is 48 and I would say that 3 will be the last two burst in this crow next let's fill up the remaining squares now we consider length 3 so this three elements starting I at 0 J at 2 so we're going to fill up this value 0 I and J 2 so we're going to try every possible value of K between I and J and see which would be the last balloon to burst initially K will be I so 0 is that if 0 is the last balloon to burst the value I can expect to get is nothing from the left of 0 from the right of zero I left it one two so I go to one two so your value of 135 plus since this button works last so one into three these two balloons are gone so into it so the total value here is 24 plus thirty one thirty five so 159 let's increment our key to one so when K is 1 if this is the last balloon traversed from the left side we get a value at zero zero so that value is three from the right side I get a value of 2 2 so that value is 40 and if this balloon bursts laughs in this growth so three and five is gone so we have 1 into 1 into 8 so this value is going to be 51 and finally K becomes J so k is 2 so if 2 is the last balloon to burst from the left side we can expect to get a value of 0 1 so equal to 0 1 so this value is 30 from the right side we get nothing because this is the rightmost end of this array and since 5 is the last value to burst 3 and 1 is already gone so we take 1 then 5 into 8 so this value is 40 plus 30 which is 70 so here 159 is the largest value so we make sure that 0 is the last balloon to burst in this group so I'm going to note 159 comma 0 now we will now we will work with the second sub array of length 3 with sots at 1 and Z 3 and our K will again go from 1 to 3 so let's do this quickly so when K is 0 and when K is I so if one is the last value to burst so we get 0 from the side from the right side to get a value of 2/3 which is 48 and if one is the last volume to burst so 3 into 1 into these balloons are gone so 1 so this value is 51 now increment K so k becomes 2 if 2 is the last value to burst from the left side I get 3 1 1 from the right side 3 3 gives me 40 and then if this is the last level to burst so 3 because these two buttons are gone so 3 into 5 into 1 so this value is 43 plus 15 so this is 58 and finally when K is 3 from the left side we get a value of 1/2 so we go to 1/2 so that's 1 35 from the right side we get a value of 0 and since it is the last volume to burst we multiply it 1 we multiply 3 because these two volumes are going to 3 into 8 into 1 because there is nothing on the right side of 1 so with the right set of 8 so we take a value of 1 so this value is again 159 so 159 and in here 3 is the last 3 should be the last balloon to work so we are also going to note that finally so we have till now salt all the sub-arrays so finally our length will become 4 and we'll at this width will find out which should what should be the order of English the balloon should be birthday and also what is the maximum value we can get your eyes 0 g is 3 so 0 3 we will fill up this particular square so he starts from 0 so k is then k 0 if this is the last balloon to burst then from the left side you get 0 from the right side to get value between 1 3 so 1 3 is 1:59 and then this is the last balloon traversed so one from the left side into three and these three buttons are gone so again one so giving me a total value of 162 if if K is 1 so if 1 is the last balloon 2 bars so from the left side I get a value of 3 from the right side I get a value of 2 3 2 3 is 48 and then if this is the last value to burst then it will be 1 into 1 into 1 so this value is 52 let's have 2 K s 2 so from the left side we go to 0 1 0 1 so value is 30 we go on the right side of kaizar 3 3 value is 40 and 1 into 5 into 1 so this value is 75 and finally if K is 3 and here the left left is 0 2 2 so 0 to 2 is 159 right side is 0 and it is the last balloon to burst everything else is gone so 1 into H into 1 giving me a total value of 167 so among all this 167 is the biggest number so we'll put it here and we'll also note that 3 should be the last balloon to burst so this is our answer 167 is the maximum value we can get by bursting the balloons in some optimized water so next let's see how we can get the order in which the balloon should be bursted we are going to backtrack in this matrix to find the order in which the balloons should be bursted we look at 167 is the maximum value you can get and also that the balloon at index 3 is the last balloon to burst some of all these guys if balloon at index 3 so it is an a spoon to burst so now with it safely in its position we are going to look at the remaining all right so the remaining array is 0-2 true so then we go to 0 to 2 and then that the next here is 0 which means that 0 is the last balloon to burst in this group so at 0 we have 3 so 3 is the last balloon to burst in this group and now with 0 gone we are looking at this sub array 1 to 2 so we have 1 to 2 and here the value is 2 so value at a balloon and index 2 is the last balloon to burst in this group so 5 is the last balloon to blood in this group and then we are left with 1 1 and then we go to 1 1 and this value is 1 so the value there is also 1 so this is the order in which the balloons needs to be bursted and for this array to get this value 167 thing here is that this time the backtracking we did was pretty linear but that would not always be the case for example if the last balloon to burst was 2 then we would have a left side of 2 and we would have a right side of true too and then in that case you might have to write a simple tree based structure or 3-way triggered 3 base recursion to find out the order it gives the balloons need to be version so the time complexity for this algorithm is o of n cube because we are finding every sub array and for every separate we are having a capo from the start and end of that submarine to find the last balloon to burst and the space complexity is off and square next let's look at the code for this algorithm the main function here is max coins bottom of DP it takes in an int array num swear elements in the numbers indicates the value of the balloon and int returns the maximum value we can get by bursting balloon in certain order first we initialize T which is a two-dimensional array where the rows and columns is same as the number of elements in this array then we take a value of L the length which goes from one till the numbers dot length and then for every value of Len over I will start from zero and go till numbers dot length minus Len and G will be I plus Len minus one so now this key here indicates that which balloon should be bursting last so we will try every k from i till j and see which bursting which balloon gives a maximum value this left and right value in issue inside this for loop when case goes from i till j our left and right value initially will be null will be 1 and if i is not 0 then left value will take the value of nums of i minus 1 and if j is not the last element and right value will take value of numbers of j plus 1 so this is for those leftmost and the rightmost element if there is nothing on the left of since there is nothing on the left of the leftmost element we take that initial value 1 and since there is nothing on the right of the rightmost element we give the value right value as 1 otherwise we get the value from the nums Irate similarly we have before and after before is both of them are initially 0 and if i is not same as case so if i is less than k then before will take a value of TF i K minus 1 and similarly if J is not same as K so say if J is greater than K then after we take the value of T of k plus 1 J and then once we have calculated all these values will calculate T of IJ which will be max of left value and two numbers of K into right value plus before plus after and and then max of this or the existing value of T IJ so basically we are right wading through all the case and see which K gives you the maximum value so let's look at this example so our array is 2 4 3 5 and then we initialize this T a two-dimensional array so initially our length is 1 so initially our length is 1 or I or I will be 0 J will be I plus length minus 1 so J will also be 0 so K will I trait from 0 till 0 so K can take only one value and if you go through the all this values in that case left will be 1 right value will get the value of a right value will get the value of 4 and before will be 0 after will be 0 so overall this value will end up becoming 2 into 4 which is 8 and will also note that we got the maximum value for K 0 similarly we will do for I 1 and J of I 1 J 1 and then K only possible value for K is 1 and here we get 24 1 similarly we got 62 and 15 3 so now our length will become 2 so now this length will increment and again we'll try for every value of I and J and for every value of K between I and J so now I is 0 and now J will be I which is 0 plus length which is 2 minus 1 so J in this case will be one now cable I trait from 0 till 1 so when K is 0 the maximum value we can get is 30 so if if zeroth element is the last balloon to burst between these two balloons 2 & 4 then the maximum value we can get is 30 and if and if if 1 is the last balloon to burst then the maximum value we can get is 20 so in this case so in this case so 30 is the higher value so we pick 30 and we also note that we get this value at at index at at k 0 next we are going to try I equal to 1 and J equal to 2 in this case the maximum value we can get 4 will be at index 1 and the value will be 100 and similarly our I will be 2 and J will be 3 and the maximum value we get is 80 at index and X 3 so after we are done doing this our length will again increment by one more and again I will become 0 and J will become I which is 0 plus length which is 3 minus 1 so J will become 2 so now our K will go from 0 till J and in this case the maximum value we got was at an index zero whose value was 110 next hour I will group I will become 1 and J will become 3 and K will go from 1 to 3 in this case again the maximum value we got is 110 at index 3 so finally length will become 4 and for the for length the maximum so and for the for length or I will be 0 J will be 3 so K will go from 0 till J 0 till 3 and here we get a maximum value of 115 for index or K 3 and finally retracing our steps back we can find out the order in which the balloon needs to be busted which is 3 4 to 5 and in here we return this value T of 0 num start length minus 1 which is the value at the top right corner the value the value for in this for this example is 115 so again the time complexity for this algorithm is o of n cube and space complexity is o of N squared so this is all I have to talk about this algorithm please like this video share this video check out my Facebook page and check out my github link thanks again for watching this video

Channel: Tushar Roy - Coding Made Simple

Views: 87,465

Rating: 4.535316 out of 5

Keywords: dynamic programming, leetcode

Id: IFNibRVgFBo

Length: 27min 22sec (1642 seconds)

Published: Wed Jul 06 2016