DP 51. Burst Balloons | Partition DP | Interactive G-Meet Session Update
HTML-код
- Опубликовано: 6 сен 2024
- Lecture Notes/C++/Java Codes: takeuforward.o...
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/take...
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.o...
You can also get in touch with me at my social handles: linktr.ee/take...
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.
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.
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..
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. ❤❤❤
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.
Hardest Problem in entire dp series i ever watched . same qn. was asked in Samsung. TY striver :)
There is no way on god's green earth anyone can comeup with this approach under pressure in an interview.
Understood. I was a bit confused at first, but then it clicked! Great explanation as always!
18:46 is the moment i was completely shocked I MEAN damn Man, this is BEST EXPLANATION SO FAR. Respect++
same
I spent whole day in figuring out the solution myself but I couldn't make it.Thank you for great explanation in simplest way.
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.
Hey Striver, Thanks for the wonderful explanation of the problem.
Can you make more videos on the logic of reverse thinking in DP?
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.
i fucking love coding because of solutions and explainations like this. god tier work.
i am now in codenation just because of you striver
In the tabulation approach, in the second for loop, we can run j from i to n.
yes
Wow-what an awesome explanation sir. Thanks for all the hard work that you put in, in making these videos.
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);
}
};
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!
UNDERSTOOD.......Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Really a great, clean, clear and concise solution.
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 it but this was the tough one. To come up with the right approach for such questions is the most difficult part.
amazing explanation to an amazing problem, thankyou. Understood!
Thanks was struggling with the problem a lot. But atleast did the tabulation myself.
Didn't understand the if(i>j) continue; statement
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!
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
kirti purswani wala burst balloon bahut acha hai. wo bhi dekhna kabhi
Understood Bro , Thanx for the wonderful explanation 👍
best question and explanation in my coding journey
Until 12:00 I understood the actual neighbor's part. But after that things were not getting clear. It felt like you skipped something
Understood! Aaaaaaaamazing as always, thank you very much!!
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!
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?
Understood ❤❤❤❤❤❤
"Minimum Cost to Merge Stones" Bhaiya please add this problem in your dp series . It's a humble request .
I have gone through a lot of solution in leetcode discuss forum but nobody has explained the intuition . This problem was asked in agoda online coding round. It's a pretty important as well as the hardest dp problem i have ever encountered.
Hi Bro , you are mega star ⭐️ in creating this kind of tech content in YT ,love you lots 🙏
US striver , Difficult one to think , If i was asked this , I would ask for a diff problem
Thankyou so much for amazing explanation Striver
Thank you so much Striver, Understood.
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
i did not understand if u are considering it the last one then why didn't you multiply with 1 instead of neighbours????
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??
9:39 this is why you are here 😹😹😹
Understood clearly need watch it 2 times
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
better explanation that than neetcode guy
As always "understood" ❤️
Damn this is extremely awesome!!!
Thanks
Thank you Striver!!Understood
Understood :)
Hard question, beautifully explained!!
Aug'3,2023 04:14 pm
i have a thought ... can we place a barrier between any 2 balloons like 1... {1,b1,1,b2,1,b3,1,b4,1,b5,1,b6,1}... so that every subproblem becomes independent? and we can calc the cost by moving 2 steps back and forth instead of 1... correct me if i am wrong...
Understood, sir. Thank you very much.
This is the best explanation out there.
Definitely understood, great explaination
GOATed explanation!
Understood, thanks.
There should be a mention in the question that you can burst any number of ballons at a time because if have to burst one ballon at a time then we have to take max of the 2 recursion calls.
Great explanation bhaiya as always
🥰
so great video, thanks
Amazing explanation striver bhaiya!!! Thank you so much for such a wonderful content
understood
Nice question... A head scratcher
Hey I solved it on my own ❤ Thankyou
Such a unique approach
Great Explanation Striver
did it on my own :)) similar approach to dp 50
U must be
If you dont want to modify the input array.
class Solution {
public int maxCoins(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public int helper(int[] nums, int i, int j)
{
if(i > j)
return 0;
int max = Integer.MIN_VALUE;
for(int k = i; k
Thanks Striver. Understood.
In leetcode it gives signed integer overflow, Can anyone explain why?
even If i store the coins and remainingCoins in long long, still this issue is there.
Understood 🎉
simply the best !
Amazing explanation !!
Thank you!
Understood!
Striver please...can you explanation of Merging Stones (leetcode hard) problem...I searched many yt channel but still confused...please help
understood!!! thank you so much sir
Thankyou sir. Understood.
The Python3 versions of the solutions exceed the time limit (TLE) on LeetCode.
thanks able to solve on my own.
On 14:0 what means by 1,5 is the range??
Thanks for the good explanation for Memoization. But tabulation explanation was poor. Please explain state in dp. What does dp[i][j] store? We require intuition for tabulation and not shortcuts.
The intuition comes from recursion, whatever i and j were in recursion, its the same in iteration as well, Since you memoize dp[i][j], you must be knowing what it means when you memoizing, its the same in iterative.
I am sorry, but people who tend to look for everything fetched on their plate end nowhere. Good luck, apply brains, everything is there in the lecture.
@@takeUforward I got it now. Thanks. I too think that I have got a bad habit of looking for everything served on my plate. Starting to correct it.
Brilliant!
hey striver..!!
can you explain boolean parenthesization probblem
next in line
UNDERSTOOD
Understood !! that I haven't understood 🙃🙃
hey striver my recursive code is giving stackoverflow, cant handle it.
Please help
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??
Understood Sir Thank u very much
Hey!!
Striver, I have a question, please. Or anyone who might help. You said we can't burst a balloon from the original array directly because that will make it have dependencies on the next element after b4 bursts. Now, what if, we burst b4, remove it out of the array, then add 1 in its place? Also we will add 1 in the next array's 0th index. Would that work?
a = [b1 b2 b3 b4 b5] (b3 BURST )-----------> vector A = 0-> ind-1 A3 BURST A.add(1); A.insert(A.begin(),1);
vector B = ind+1 -> n B.add(1); B.insert(B.begin(),1);
cost = f(1,A.size()-1) * a[ind] * f(1,B.size()-1);
P.S.: I haven't tried this code. It is a question of why won't this work? Please if anyone knows, may you help me out?!
AND THANK YOUUU STRIVER FOR THE AMAZING VIDEOSS!!!!!!
Understood BTW its just similar to cut the stick problem😂😂
thank you !!
class Solution {
public:
//Very minor changes to 1547. Minimum Cost to Cut a Stick Problem
// Which baloon should I burst first? -------> WRONG APPROACH -----> dependant subproblems
// Let this baloon be the last baloon to be burst ----> CORRECT
int func(int left,int right,vector& cuts,vector& rod,vector& dp)
{
if(left>right) return 0;
if(dp[left][right]!=-1) return dp[left][right];
int ans=INT_MIN; //CHANGE
for(int cutatindex=left;cutatindex
Nice one !!!
the explanation is excellent
Can you please explain how to know that a question requires a partial DP approach?
Good question. Did you find the answer?
@@aryansinha1818 no
THe questions that have to be solved in a particular way are usally solved using partition dp.
These questions may have different answer depending on the way we solve eg maths equation with bracket and without bracket,MCM etc
multiple way to solve and have to find the best way to solve.
@@aryansinha1818 THe questions that have to be solved in a particular way are usally solved using partition dp.
These questions may have different answer depending on the way we solve eg maths equation with bracket and without bracket,MCM etc
multiple way to solve and have to find the best way to solve.
Understood
Understood, thank you bhaiya.