DP 51. Burst Balloons | Partition DP | Interactive G-Meet Session Update
Vložit
- čas přidán 21. 04. 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3Kgck9N
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the burst balloons problem which is a part of partition DP.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
Your videos have helped me to get to Google. Thanks a lot for making such helpful stuffs.
Bhaiya can you Kindly say how much does cp profile matter for google at 1-2 years of experience? Thank You very much... 🙏
@@abh9789 I didn't had any. I solved the SDE sheet religiously and followed his videos and some other folks videos (techdose and codebix).
@@gopeshkhandelwal9823 May I ask which college are you from? Did you join google as a fresher? Thank You..
@@abh9789 No, I am not a fresher. I had worked with Amazon for 1.5 years earlier after the college.
You proved that we don't need scaler.
This video has saved me two days of scratching my head while trying to understand the solution in discussion section and still moving on with unclear things in my head
The fact that there were no courses like this to learn from during his time and he must have learnt all this with just pure grind and just hours and hours of work blows my mind.
He's pouring his years of hard work into these videos and that too for free
Thank You Striver !
At 22:36 there is mistake it will be mini = max(mini, cost)
yes upvote every one so that everyone can see this mistake👍
i think striver wanted to use maxi = max(maxi, cost) like he uses always
yah its maxi we need. Just a small mistake guys. it happens at times
Anyways the point is we need to go in reverse - last 2ndlast 3rdlast....nthlast(aka first)
Understood, thanks.
Again, this seems to be straight forwardly explained but there's a huge R&D which you might have done to come up with the solution. Thanks a ton for all the help!
Yups, true.
Striver, in the tabulation method, you don't need to check the condition (i > j continue), you can start the jth loop from i, and it will work fully fine. Thanks for making such great videos. This DP playlist is the best gift from your side to the community.
I have done the same..
There is no way on god's green earth anyone can comeup with this approach under pressure in an interview.
one of the toughest problem so far for me, but as soon as you explained the approach of going from last balloon to first balloon, i was able to code it up myself. All this due to your excellent dp series so far!
Same. The moment he said it, the whole solution struck me. Sadly, I could not come to the conclusion myself.
Understood. I was a bit confused at first, but then it clicked! Great explanation as always!
This is one of your best videos!
Burst Balloons has got to be one of the most complex problems for anyone solving it for the first time, and your explanation makes it clear how the methods we would normally begin with won't work, and why starting from the bottom WILL work.
Thanks for this video and congrats for making a great one for this problem. ❤❤❤
Really a great, clean, clear and concise solution.
Wow-what an awesome explanation sir. Thanks for all the hard work that you put in, in making these videos.
Hardest Problem in entire dp series i ever watched . same qn. was asked in Samsung. TY striver :)
This is one of your best videos!
Burst Balloons has got to be one of the most complex problems for anyone solving it for the first time, and your explanation makes it clear how the methods we would normally begin with won't work, and why starting from the bottom WILL work.
Thanks for this video and congrats for making a great one for this problem.
Understood! Aaaaaaaamazing as always, thank you very much!!
UNDERSTOOD.......Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thank you so much Striver, Understood.
aaj tak burst balloons nhi samajh paya tha itne logon ki videos dekhi youTube par but apki video se 1 shot me samajh aagya thanks bhai and understood!!! ofc.
Hey Striver, Thanks for the wonderful explanation of the problem.
Can you make more videos on the logic of reverse thinking in DP?
Thankyou so much for amazing explanation Striver
Understood Bro , Thanx for the wonderful explanation 👍
i am now in codenation just because of you striver
GOATed explanation!
Understood, thanks.
simply the best !
18:46 is the moment i was completely shocked I MEAN damn Man, this is BEST EXPLANATION SO FAR. Respect++
same
Thank you!
Understood!
Understood ❤❤❤❤❤❤
understood it but this was the tough one. To come up with the right approach for such questions is the most difficult part.
Read many solution where they just told that it's MCM add 1s to start and end that's it, but I didn't find it intuitive...
This solution is logical rather than mugging up those solution!
Thankyou sir. Understood.
Didn't understand the if(i>j) continue; statement
I never learnt dp in scaler like this. I never knew the recursive version in scaler went with tabulation. Striver bhaiya big fan of you I can shout from top of house you made me learn dp like anything. Even during time of scaler i got rejected in first round of amazon. Now I had cleared three rounds maang is a dream for me you will make it come to reality
Hi, is scaler worth it or not?
did you get maang? how are you doing nowdays.
In the tabulation approach, in the second for loop, we can run j from i to n.
yes
Hi Bro , you are mega star ⭐️ in creating this kind of tech content in YT ,love you lots 🙏
Thank you Striver!!Understood
Definitely understood, great explaination
Nice one !!!
best question and explanation in my coding journey
understood!!! thank you so much sir
thank you !!
Understood, sir. Thank you very much.
This is the best explanation out there.
Understood clearly need watch it 2 times
if in any interview a guy faces this type of questions for the first and able to come up with a solution at that point because the previous video has helped with the fact that why serial wise approach wouldnot help but thinking of the backward approach is tough
Understood bhaiya!!
Just a small enhancement, we do not need to check the condition (i>j) , we can start j from i, and the code will work fine.
int maxCoins(vector& nums) {
nums.insert(nums.begin(),1);
nums.push_back(1);
int n=nums.size();
vector dp(n,vector (n,0));
for(int i=n-2;i>=1;i--)
{
for(int j=i;j
Hey I solved it on my own ❤ Thankyou
Understood 😊
As always "understood" ❤️
Amazing explanation striver bhaiya!!! Thank you so much for such a wonderful content
Understood🔥
UNDERSTOOD
understood
kirti purswani wala burst balloon bahut acha hai. wo bhi dekhna kabhi
Amazing explanation !!
thanks able to solve on my own.
Understood
No need to insert 1 at the end and start, you can just check if i and j are at the boundary before calculating the product. This is the memoised code, you can surely do the tabulation by now
class Solution {
public:
int solve(int i, int j, int n, vector &nums, vector &dp) {
if(i>j) return 0;
if(dp[i][j]!=-1) return dp[i][j];
int ans = INT_MIN;
for(int k=i;k= n) ? 1 : nums[j+1]; //if j+1 is out of bounds
int coin = left*nums[k]*right + solve(i,k-1,n,nums, dp) + solve(k+1,j,n,nums,dp);
ans = max(ans, coin);
}
return dp[i][j] = ans;
}
int maxCoins(vector& nums) {
int n = nums.size();
vector dp(n, vector (n, -1));
return solve(0,n-1,n,nums,dp);
}
};
Bro ,u can use backtracking like keep bool array for bursted balloons ,and then calculate from top to down itself
Yes, you can, but you cannot apply Memoization to it!
Damn this is extremely awesome!!!
Thanks
did it on my own :)) similar approach to dp 50
U must be
Thanks Striver. Understood.
Until 12:00 I understood the actual neighbor's part. But after that things were not getting clear. It felt like you skipped something
Such a unique approach
Understood :)
Hard question, beautifully explained!!
Aug'3,2023 04:14 pm
Got it bro.
Go fast
better explanation that than neetcode guy
Understood , #Chamka
Great Explanation Striver
Understood Sir Thank u very much
Nicee
Understood, thank you bhaiya.
Brilliant!
U r amazing striver!!
9:39 this is why you are here 😹😹😹
👍🏻🔥 thank you
the explanation is excellent
In ur insta post u mentioned it will be the biggest DP series, how many videos left
Nice question... A head scratcher
yes understood bro great explanation
Perfect
i did not understand if u are considering it the last one then why didn't you multiply with 1 instead of neighbours????
Bhaiya in Tabulation in the second nested loop why are we starting from j=1 and not j=i+1??? our j will always be on the right side of i isn't it? (just like in the last examples of partition dp)
Yes, u can, i just wrote a genric way, and then used the if statement inside
Understood 🎉
what app do you use to record screen and for white board?
Non intuitive not a single thought came to solve it like this even after knowing that it requires MCM 😭😭 .
had to watch video for solution
The Python3 versions of the solutions exceed the time limit (TLE) on LeetCode.
Hey Striver Bhaiya, I have a doubt:-
Why can't we follow it as we should leave both the numbers on the extreme ends. and from the left numbers we should start bursting the number which is the smallest. then 2nd smallest then 3rd and so on till the last number in between the both the extreme numbers ends. And then from the number which are last two extreme burst any one one of them first and and left number 2nd.
eg:- [ 4,6,8,5,3,2,1,9]
If this is the set remove the two numbers at the extreme ends:- 4,9 [6,8,5,3,2,1]
Then start bursting the smallest number in the left set:- so the first number will be '1' == 2*1*9=18 4,[6,8,5,3,2],9
then '2'== 3*2*9=54 4,[6,8,5,3],9
then '3'== 5*3*9=135 4,[6,8,5],9
then '5'== 8*5*9=360 4,[6,8],9
then '6'==6*8*9=432 4,[8],9
then '8'==4*8*9=288 [4,9]
then left are 2 numbers which are 4,9. Now burst any number first let say I burst '4'==1*4*9=36 [9]
then '9'==1*9*1=9 [ ]
Total Sum=1332 and it will be maximum.
Why can't we code using this method??? I am a FIRST YEAR STUDENT.
can this approach works for all cases??
wow
Understood !
Hi striver. First of all thanks for the explanation. I understood the explanation but when i looked at the code it is exactly similar to other problems we did[say l49 or l50] which were done in a top down approach. So i don't understand how the code is the same for which ever approach we take. If i looked at the code directly without looking at your explanation, i would think we are solving this problem exactly as we did for mcm or break stick problem which should not be the case as the approaches for the problems are totally different. Please help me understand this part. Thank you!
understood!!
US striver , Difficult one to think , If i was asked this , I would ask for a diff problem
Mast hai sir aapka explanation, maja aa gya😀
THIS PROBLEM IS JUST AN MCM problem. I find this explanation a bit complicated than that approach.
You just need to add 1 at the beginning and at the end, then just copy paste the same MCM code with the condition changed from finding min to max and that will work.
I think you can see why, if anyone is facing issue let me know here, I'll explain.
how it is working, can you share your code?
Nice content 😊👍
Can anybody tell why we are sorting the array in Min cost to cut stick and not in this?
And how to know when should we sort the array and when to not??
kya explain kiya hai bhai..amazing
Understood!!!!
Top class video... ❤
Understood!!