I have to watch editorial literally every time it is a dp problem. At this point, I am thinking may be dp is not for me. I get stuck in finding the way to get to the base case and through which viewpoint.
How do we visualize looping from the last book in the second solution? Are we starting with the last book in the first shelf and then slowly building off that? Or are we imaging the last book being on some arbitrary top shelf
I could think of two parameter based recursive function, but I don’t think I could have thought of considering the shelf number as parameter. There is no logical flow from first to second, it is just practice I am guessing
When cur_width < width, we break out of the for loop. But what if the subsequent book eg. books[j+1] can fit into the current shelf? Do we not have to consider that?
I solved with multiple parameters but then when I tried to cache it I wasn't able to do it. Pretty interesting that I can try the path to remove parameters somehow.
The recurrence relation is intuitive - I got it down pat except when I tried to follow your solution, I had to rewind and watch it multiple times. Nothing on you, it's just one of those problems where you get it but when you're translating it to code you're stuck.
He’s fast with it, my initial solution was O(n^2logn) 😢 I misread the question as that we could reuse the previous bucket but we just go in orders so I had to track all the previous buckets
DP is not exactly brute force. Though ofc it's easy to recognize it after seeing it a bunch of times and doesn't require much thought if you understand it. But that's basically all Leetcode Easys and Mediums. On the other hand, the majority of average devs probably wouldn't realize it, if they even know DP at all.
My foolish self thought this could be solved using greedy algorithm running from the front and the back and then get the min of the two totalHeights 😅😅😅
Same but slightly different, I thought about using a max heap to find out the biggest two heights within a gap of shelf width then determine if the max in current shelf is below the 2nd biggest, if it is then we can't put the largest book in the current shelf
Anything that you thought could be more clear? The whole idea is for every recursive call helper(i) we are starting at a new shelf and start at books[i]. Everything else can be derived from there. I made sure to mention this multiple times throughout the video.
There are time stamps if you wanna skip to specific parts. Is there anything specific you thought was redundant? Generally dynamic programming videos are always longer since they have multiple solutions.
I love how you keep going back to your 150, honestly I also recommend the same to everyone that asks me.
Kudos! Nice explanation!
The way you erased the entire question was really funny
I find the combining part really confusing using a bottom-up approach. Solving it in recursive is way more easy to understand for me!
I have to watch editorial literally every time it is a dp problem. At this point, I am thinking may be dp is not for me. I get stuck in finding the way to get to the base case and through which viewpoint.
How do we visualize looping from the last book in the second solution? Are we starting with the last book in the first shelf and then slowly building off that? Or are we imaging the last book being on some arbitrary top shelf
I could think of two parameter based recursive function, but I don’t think I could have thought of considering the shelf number as parameter. There is no logical flow from first to second, it is just practice I am guessing
this exactly. also could you show your 2 variable solution ?
Identifying which pattern to use... Still the hardest part that makes me fail
Thanks for the clear explanation Neet!
2nd! Thanks! My mind was freeze until watching your video!
hey man! How does one become as eloquent as you? Imagine being this eloquent in an interview? Damn!
Don't get discouraged, he's a good programmer but his video solution is very prepared and organized.
Thought binary search would work here. Worked out a few examples and figured, partitions using DP is more like it.
Amazing time complexity explanation
How can you get the intuition for line 17
res = min(res, maxHeight+helper(j+1) ??
When cur_width < width, we break out of the for loop. But what if the subsequent book eg. books[j+1] can fit into the current shelf? Do we not have to consider that?
no because we gotta place the books in order
Great explanation as always. Thank you
Great explanation !
I solved with multiple parameters but then when I tried to cache it I wasn't able to do it. Pretty interesting that I can try the path to remove parameters somehow.
Great explanation!!
The recurrence relation is intuitive - I got it down pat except when I tried to follow your solution, I had to rewind and watch it multiple times.
Nothing on you, it's just one of those problems where you get it but when you're translating it to code you're stuck.
He’s fast with it, my initial solution was O(n^2logn) 😢
I misread the question as that we could reuse the previous bucket but we just go in orders so I had to track all the previous buckets
Before I forget, i don't know if the 2nd solution is this or what,
but i thought if we start from last, and like use greedy, then it will work...
Wondering what if the Books can be put on shelf NOT in order and find MIN height?
Intuition of Partition dp
The time then Padawan defeated his Master. :)
i really hate when they give us these type of problems like where is the critical thinking when the brute force is the most optimal solution
DP is not exactly brute force. Though ofc it's easy to recognize it after seeing it a bunch of times and doesn't require much thought if you understand it. But that's basically all Leetcode Easys and Mediums. On the other hand, the majority of average devs probably wouldn't realize it, if they even know DP at all.
brute force is trying out all the possible permutations of the books and picking the least height
My foolish self thought this could be solved using greedy algorithm running from the front and the back and then get the min of the two totalHeights 😅😅😅
Same but slightly different, I thought about using a max heap to find out the biggest two heights within a gap of shelf width then determine if the max in current shelf is below the 2nd biggest, if it is then we can't put the largest book in the current shelf
17:00 ηρεμησε μπρο
I don't understand why people say the question isn't clear everytime
I think the question is clear enough and doesn't miss anything
It doesn't say anything about reusing the shelf empty slots. I had to literally make up and run two test cases just to confirm this.
navdeep paaji please spare us noobs
why can't we put "3" at the first row and shift "4 5 6 7" one step to the above row, so that the answer for the given example would be 5 instead of 6.
The shelf is only 4 wide. Books 1-3 togheter are 5 wide.
the explanation couldn't have been more confusing tho
Anything that you thought could be more clear?
The whole idea is for every recursive call helper(i) we are starting at a new shelf and start at books[i]. Everything else can be derived from there. I made sure to mention this multiple times throughout the video.
@@NeetCodeIO Hey thanks for this comment,Initially we are placing a book in new shelf and then combining them from the first shelf to last shelf?
again this month? why??
Day 0 of asking dry run of code by diagram.
Isn't that something you can do yourself? I promise you will understand it better if you do. I didn't get good by watching videos.
1st
dam that was fast
@@NeetCodeIO lol sry for creeping
Man I really try to watch these, but the amount of bloating just to make the videos longer is maddening..
There are time stamps if you wanna skip to specific parts. Is there anything specific you thought was redundant?
Generally dynamic programming videos are always longer since they have multiple solutions.