I want to req u to plz do not think that ur vedio length is getting big and mess up we are here to learn no matter time we are here for quality and u are known for it so plz do make such vedios it's fyn 💯🤌 @take U forward
"vector &points" Why does passing points as reference make a difference. When i was passing Points with out reference the i got TLE for some test cases. BUT passing by refernce passed for all test cases.
Understood Sir ! I noticed You submit Memoization code at 03:52 AM then Tabulation at 04:09 AM and lastly Space optimization At 04:26 AM...what a effort You are giving us to understand these concepts. Thanks a lot Sir.
At 24:00 ... i think there is a small mistake in the return value of f(1,2) .🙂 It should be 7 instead of 6 because we are storing maximum 🙏 But overall whole video is amazing 🔥🥳
I am 25 y/o and have been trying to learn DP for last 5 years now, referred multiple materials but this time, I have a strong hope I am gonna make it out of tutorial loops. Man, this material is premium. 💙 We gonna make it bros!
I think in the tabulation code we should rename last to next (makes it easier to understand) , because in tabulation we are going reverse order we are filling the current row of dp array based on assumption that in next row the given activity is selected , this is also the reason why at each index dp[index][3] stores the answer uptill now because for next=3 we can select anything . This took me 4 hours to understand lol ,incase there 's someone else like I do hope you read this and not waste your time.
Thanks yrr, this thing took me a lot of time to understand too, I was so confused why are we keeping dp[day][3(last)] . Because we can have last as 3 only for the first day, from the second day last would never be 3 again. But here the assumption is, dp[day][3] ----> Max point acquired till "day" while at "day+1" no task is performed.
Thanks, guys this was helpful, but I could not understand 1 part that Sayan also mentioned that for Base Case on day 0, how we can take a task dp[0][3] // dp[0][3] -> this will mean that no task is planned for the next day But this can only be possible on the nth day -> this case cannot be possible before that -> so how it is written in the base case.
@@VarshaSingh-hi2sb Because he is using 0,1,2,3 as lastUsedIndex. Lets say f(n, lastUsedIndex) -> means maximum value at day n, when you selected lastUsedIndex on day n+1th. f(2,0) -> maximum value at day 2, when we selected 0th index on day 3. (This is recursion going from n-1 to 0, so you are technically going backwards, hence you are worrying for the day ahead of you) Now value 3 is only used when we are at the start of recursion i.e. at n-1th index. Because at n-1th index we can chose any element as nth element doesn't exists(Here n is the size of the vector). Hence the size is 4 to handle these such cases.
It's magical to realize and see that a question that seemed unsolvable to me at first, can be solved so easily and even be space optimized so beautifully. You're the best DSA teacher ever.
That's right but it wont make a difference since the max function would choose the max between the 2 values and therefore 8 would be returned back anyways
How about this : Code is self explanatory int ninjaTraining(int n, vector &points) { int pre1=points[0][0], pre2=points[0][1], pre3=points[0][2]; int cur1, cur2, cur3; for(int i=1; i
damn it! Before the start of this DP series i was just thinking of this series to be like any another dp series but watching this video completely changed my mind. Truly the best dp series out there and the best part is that it has just begun.Looking forward for the next lecture.Thanks for making dp this interesting and fun.
Understood Thanks for the amazing content. I solved this problem on my own but yeah! I still completed the video for understanding your approach. my optimized code complexity:- Time = O(n) [ run only a single for loop ] Space = O(1) [ used 6 variables only ] int ninjaTraining(int n, vector &grid) { int task1 = grid[0][0] , task2 = grid[0][1] , task3 = grid[0][2]; int prevTask1 = task1 , prevTask2 = task2 , prevTask3 = task3; for(int day=1;day
Exactly we could have taken only three space not required 0-3 when using tabulation although last 3 variable that you are taking is the same as dp[i-1] or prev when using space optimization no need to make it complex by taking 6 variable by the way. Nice work !!!!
Understood The problem can be solved in O(3) space complexity instead of O(4) - though it doesn't matter that much. Also, at 44:01 on line 31, the statement doesn't take the max of all three values in points table. If you look closely, striver bhaiya may have mistakenly taken points[0][1] twice and there may not have been any test case for which the code fails. None the less, amazing effort bhaiya! 👌🔥
is tabulation mandatory ? i think maximum problems can be solved with memoization and that too in interview interviewers get satisfied with memoizaion technique since they give uto 45min. for such questions.
This line is important if you have n(days) as 1 public int maximumPoints(int points[][],int N){ int[] prev = new int[3]; points = points; prev[0] = Math.max(points[0][1], points[0][2]); prev[1] = Math.max(points[0][0], points[0][2]); prev[2] = Math.max(points[0][0], points[0][1]); int[] temp ; for (int day = 1; day < N; day++) { temp= new int[3]; for (int last = 0; last < 3; last++) { for (int task = 0; task < 3; task++) { if (task != last) temp[last] = Math.max( temp[last] , points[day][task] + prev[task]); } } prev = temp; } return Math.max(Math.max(prev[0], prev[1]), prev[2]); }
I am so hyped for this! After finishing the 1 DP series, I can solve almost any 1 DP problem whereas before I could barely solve any! Can't wait to solve 2D DP problems now 😃
Hey Striver! I have already seen and practiced your recursion series. It literally has helped me to write the recursive code by myself. Even in this question , I was able to figure out the recursive code before watching the entire video. Literally, there is something unique in your teaching style.
I started watching the video, figured the recursion, immediately paused the video and started coding it. Wrote the base case just as you said, if(index < 0) return 0; but then I resumed the video and saw him doing this. Nevertheless, go the same output for both the ways. But I guess this is to increase the efficiency a tad. Though glad to know that you tried it too 🙌🏼 Having said tat, this guy is simply amazing! I love the way he teaches and truly admire him ❤
Thank you Striver for this video. I used to struggle a lot with DP and 2D DP was something that I never understood. But after watching this video, I was able to solve a 2D DP problem using all 4 ways - Recursion, Memoization, Tabulation and Space Optimisation.
approach is clear. just a doubt that in dp[][4]= nothing will store so why to create a 4 size beacuse every time we have to do some activity so for next the last will definitely exist.
because to confirm that the start case will contain all the possibility, as giving any valid index will not allow us to start with all possibilities on the first iteration.
@@shubhanshukumarsingh6133 basically storing an extra index will work if we want to work on function based on sizes... the approach at whivh we handle how our argument work onto is the deciding factor
@@anshulrawat3458 when in first iteration from top to down we need all valid options so we'll pass 3 as last and if dp is of size 3 i.e. till 2 index then it'll miscompute. So dp size of 4 is mandatory for first iteration in memoization.
Hey Striver, The memoization approach doesn't work completely. it passed fo 10/11 test cases and gave stack overflow for the 11th one. This is for Java, I even tried the solution on TUF website. Thanks :)
OMG, Literally no one on RUclips is like you Bhaiya. From now onwards for DP your playlist would be referred as that for Graph. Thank you Bhaiya for heling us.
🤯 I must say apart from being an ace developer, you are very very skilled teacher. Teaching is not everyone's cup of tea, but you my friend can make us understand even rocket science. (Try creating its playlist as well 🤣).
//I read the question and tried to solve it by myself and I came to this solution. (All testcases are getting passed) #include using namespace std; int solve(int row, int c, int prevIndex, vector &v,vector &dp) { if(row==v.size()) return 0; int maxVal=INT_MIN; if(dp[row][prevIndex+1]!=-1) return dp[row][prevIndex+1]; for(int col=c;col
We can shorten the base case in Recursion and Memoization: if(day == -1) return 0; This works because adding 0 to the current sum, doesn't change the sum.
But I think in tabulation line 31 At 41:00 dp[0][3] = max(points[0][0],max(points[0][1],points[0][2]) But the striver missed points[0][0] when he coded Correct me if I am wrong!
Thank You so much for making these videos, it has been really helpful during placement season. The method of explanation makes it so easy to understand and grasp these concepts even thought it is my first time learning DP. At 24:03 just wanted to make sure that 7 should be returned and not 6 from f(1,2)
sir, in the recursion code, actually you don't need to write another loop to get max, you can go one step behind and return 0 for that as base case, and let the recursion find last max for you. int maxPoint(int day, int prevTask, vector &points ){ if(day
hey brother i have a doubt I have gone from index 0 to n-1 and couldnt figure out to use MEMO It would be a great help to me if You can help to find the right appraoch class Solution { private: int MaxSum (vector &arr, int i, int last_index ,vector &dp) { //base case if (i == arr.size()) return 0; //recursive case //dp part if (last_index == -1 && dp[i][last_index] != -1) return dp[i][last_index]; int ans = 0; for (int j=0; j
By far hats down this is the best DP video explained intuitively. Thanks a lot, Striver. . BTW if you remember me, I have been your old subscriber. . Thanks a lot again!!!!!!
For tabulation, if the current tasks == 0, on day 1, DP holds the maximum possible value from the previous day, excluding task 0. That's how base cases are formed.
One Greedy approch will be to put all the cells value along with day and Task ( points, rowNo, ColNo) in in max heap. Also keep track of what task was greddily picked on that that day. Now when we pop an item from maxheap we do comparison with its neighbouring days In the first eg: First we get (100, 1, 1) from max heap, daysPoints = -1| (100,1,1) next we will get (50, 0,1) from max heap , but on checking the 0th day nbr in array: daysPoints , we find that we already did the same task. So we ignore this next we will get (11, 1,1) from max heap , but on checking the 1st day in array: daysPoints , we find that we already slected one => ignore next we will get (10, 0,0) from max heap , on checking the nbr on 0th day in array: daysPoints , we find that the same task was not chosen so we add it in array: (10,0,0) | (100,1,1) Finally we sum the points.
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.
make a video on time and space complexity from basics to advanced
I want to req u to plz do not think that ur vedio length is getting big and mess up we are here to learn no matter time we are here for quality and u are known for it so plz do make such vedios it's fyn 💯🤌 @take U forward
@SACHIN SHARMA everyone will have a different thought process, there is no hard and fast rule for base cases!
at 24:04 time, In recursion tree f(1,2) should be 7 as it is max of (6,7).Pls validate it. thanks for video. keep it up.
"vector &points" Why does passing points as reference make a difference. When i was passing Points with out reference the i got TLE for some test cases. BUT passing by refernce passed for all test cases.
Understood Sir ! I noticed You submit Memoization code at 03:52 AM then Tabulation at 04:09 AM and lastly Space optimization At 04:26 AM...what a effort You are giving us to understand these concepts. Thanks a lot Sir.
❤️
@@takeUforward when do you sleep then ?
@@asutoshghanto3419 maybe he recorded on weekends
@@yyvaibhav No its his regular routine.. He records lec late night and sleeps around 4-5 😅
(Hard work op ..)
He told about this in pune seminar
This man is insane
At 24:00 ... i think there is a small mistake in the return value of f(1,2) .🙂
It should be 7 instead of 6 because we are storing maximum 🙏
But overall whole video is amazing 🔥🥳
That's correct. He's recording this at late night. That's why.
thanks
yeah that's right 7 for a reason....
I am 25 y/o and have been trying to learn DP for last 5 years now, referred multiple materials but this time, I have a strong hope I am gonna make it out of tutorial loops. Man, this material is premium. 💙
We gonna make it bros!
did you?
@@nidhishprasad2506 U doubt?
@@gyanunlimited740 No, it's great. I was asking you if you are able to solve dp problems now?
@@nidhishprasad2506 Better than ever before
im also 25 and learning dp
I think in the tabulation code we should rename last to next (makes it easier to understand) , because in tabulation we are going reverse order we are filling the current row of dp array based on assumption that in next row the given activity is selected , this is also the reason why at each index dp[index][3] stores the answer uptill now because for next=3 we can select anything . This took me 4 hours to understand lol ,incase there 's someone else like I do hope you read this and not waste your time.
Thanks yrr, this thing took me a lot of time to understand too, I was so confused why are we keeping dp[day][3(last)] .
Because we can have last as 3 only for the first day, from the second day last would never be 3 again. But here the assumption is, dp[day][3] ----> Max point acquired till "day" while at "day+1" no task is performed.
right, i also got stuck there, after some time I get it little clear in my mind.
it took me as much time to understand the tabulation as it did not take me time to understand the entire video.😪😪
Thanks, guys this was helpful, but I could not understand 1 part that Sayan also mentioned that for Base Case on day 0, how we can take a task dp[0][3]
// dp[0][3] -> this will mean that no task is planned for the next day
But this can only be possible on the nth day -> this case cannot be possible before that -> so how it is written in the base case.
@@mayanksaurabhmayanksaurabh9271 did you got that??
28:18 love how his declaration coincided with the lights going out. Thanks for the content as always
Why dp array is declared with size 4? And how the time complexity is O(N*4)*3?
@@VarshaSingh-hi2sb Because he is using 0,1,2,3 as lastUsedIndex.
Lets say f(n, lastUsedIndex) -> means maximum value at day n, when you selected lastUsedIndex on day n+1th.
f(2,0) -> maximum value at day 2, when we selected 0th index on day 3. (This is recursion going from n-1 to 0, so you are technically going backwards, hence you are worrying for the day ahead of you)
Now value 3 is only used when we are at the start of recursion i.e. at n-1th index. Because at n-1th index we can chose any element as nth element doesn't exists(Here n is the size of the vector). Hence the size is 4 to handle these such cases.
@@VarshaSingh-hi2sb dp array size depends on input array size u can take same as input
There are many paid courses teaching DP but you're only one teaching the mindset to solve DP problems. Big respect and love from Tamilnadu🙏
It's magical to realize and see that a question that seemed unsolvable to me at first, can be solved so easily and even be space optimized so beautifully. You're the best DSA teacher ever.
At 24:07, I think we will be taking the value 7,instead of 6.Correct me if I am wrong. Awesome video as always.
Exactly it should be 7
Yaa that should be 7@@Aladin40chor
That's right but it wont make a difference since the max function would choose the max between the 2 values and therefore 8 would be returned back anyways
Yeah bro it must be 7.
@@antibarcelona2123 the max returned would be 14 and not 12. max((8+1), (7+6)). So it does make a difference
It is really a tough question for everyone whoever sees 2D DP for the very first time, but striver is here to make everything easy for us.
indeed!
This question is quite hard.
us. What an explanation from memoization -> tabulation -> space optimisation. Terrific and totally unique. Thanks Striver.
How about this :
Code is self explanatory
int ninjaTraining(int n, vector &points)
{
int pre1=points[0][0], pre2=points[0][1], pre3=points[0][2];
int cur1, cur2, cur3;
for(int i=1; i
correct was thinking the same why not keep in variables instead of array
same thing i guess. won't change the complexity of O(4). Cause you are essentially using 4 variables
damn it! Before the start of this DP series i was just thinking of this series to be like any another dp series but watching this video completely changed my mind. Truly the best dp series out there and the best part is that it has just begun.Looking forward for the next lecture.Thanks for making dp this interesting and fun.
Thankyou for commenting so late at night.
No one teach space optimization. I learn space optimization by watching your videos. Thank you so much for providing this course.
What an explanation from memoization -> tabulation -> space optimization woww Terrific
That striver on hand at 26:50 was literally 🔥
sir at 24:04 it should return 7 right and not 6 . btw thankyou for your efforts us !! .
Ri8
Yes
Yes , because f(i,j) means , maximum points on day i when previously task j was done.
i was gonna point it but thanks
yeah
"Us", the best video on DP, nobody I say nobody could explain like you did, Thanks alot.
Understood
Thanks for the amazing content.
I solved this problem on my own but yeah! I still completed the video for understanding your approach.
my optimized code complexity:-
Time = O(n) [ run only a single for loop ]
Space = O(1) [ used 6 variables only ]
int ninjaTraining(int n, vector &grid)
{
int task1 = grid[0][0] , task2 = grid[0][1] , task3 = grid[0][2];
int prevTask1 = task1 , prevTask2 = task2 , prevTask3 = task3;
for(int day=1;day
Exactly we could have taken only three space not required 0-3 when using tabulation although last 3 variable that you are taking is the same as dp[i-1] or prev when using space optimization no need to make it complex by taking 6 variable by the way. Nice work !!!!
Understood
The problem can be solved in O(3) space complexity instead of O(4) - though it doesn't matter that much.
Also, at 44:01 on line 31, the statement doesn't take the max of all three values in points table. If you look closely, striver bhaiya may have mistakenly taken points[0][1] twice and there may not have been any test case for which the code fails.
None the less, amazing effort bhaiya! 👌🔥
Exactly! I had the same thought!
Yes right. I noticed it also.. Thanks for pointing out.
is tabulation mandatory ? i think maximum problems can be solved with memoization and that too in interview interviewers get satisfied with memoizaion technique since they give uto 45min. for such questions.
@Gaurab Das.Can u explain how??
This line is important if you have n(days) as 1
public int maximumPoints(int points[][],int N){
int[] prev = new int[3];
points = points;
prev[0] = Math.max(points[0][1], points[0][2]);
prev[1] = Math.max(points[0][0], points[0][2]);
prev[2] = Math.max(points[0][0], points[0][1]);
int[] temp ;
for (int day = 1; day < N; day++) {
temp= new int[3];
for (int last = 0; last < 3; last++) {
for (int task = 0; task < 3; task++) {
if (task != last) temp[last] = Math.max( temp[last] , points[day][task] + prev[task]);
}
}
prev = temp;
}
return Math.max(Math.max(prev[0], prev[1]), prev[2]);
}
understood properly and process of recursion to space optimization is amazing ❤
I am so hyped for this! After finishing the 1 DP series, I can solve almost any 1 DP problem whereas before I could barely solve any! Can't wait to solve 2D DP problems now 😃
is there a small mistake at 24:01 ...we should go with 7 instead of 6 right ??
Yes we should get 7 as max but mistakenly wrote 6..
the best teacher in dsa ... want like these contents in java completely
Hey Striver!
I have already seen and practiced your recursion series. It literally has helped me to write the recursive code by myself. Even in this question , I was able to figure out the recursive code before watching the entire video. Literally, there is something unique in your teaching style.
Space optimization using variables (Java) :
private static int ninjaTrainingSpaceOptimized(int n, int[][] points) {
int c1 = points[0][0], c2 = points[0][1], c3 = points[0][2];
for(int i = 1; i < points.length; i++) {
int n1 = Math.max(c2, c3) + points[i][0];
int n2 = Math.max(c1, c3) + points[i][1];
int n3 = Math.max(c1, c2) + points[i][2];
c1 = n1;
c2 = n2;
c3 = n3;
}
return Math.max(c1, Math.max(c3, c2));
}
You are simply Commendable Striver!!! Always grateful to you!!!
Just when Striver said "Just remember this and you can solve any problem in the world !", Electricity did a mic drop on behalf of Striver OP.
in the top down approach, i feel instead of writing that much code for day==0 case we can just return 0 for day
I started watching the video, figured the recursion, immediately paused the video and started coding it. Wrote the base case just as you said, if(index < 0) return 0; but then I resumed the video and saw him doing this. Nevertheless, go the same output for both the ways. But I guess this is to increase the efficiency a tad. Though glad to know that you tried it too 🙌🏼
Having said tat, this guy is simply amazing! I love the way he teaches and truly admire him ❤
100%
Thank you Striver for this video. I used to struggle a lot with DP and 2D DP was something that I never understood. But after watching this video, I was able to solve a 2D DP problem using all 4 ways - Recursion, Memoization, Tabulation and Space Optimisation.
good series, just after 6 lectures, I was able to do this question on my own.
approach is clear.
just a doubt that in dp[][4]= nothing will store so why to create a 4 size beacuse every time we have to do some activity so for next the last will definitely exist.
because to confirm that the start case will contain all the possibility, as giving any valid index will not allow us to start with all possibilities on the first iteration.
@@sumitsoni2713 oh got it
@@shubhanshukumarsingh6133 basically storing an extra index will work if we want to work on function based on sizes... the approach at whivh we handle how our argument work onto is the deciding factor
but it is running without making that. u were correct, its extra effort only. we only require valid index
@@anshulrawat3458 when in first iteration from top to down we need all valid options so we'll pass 3 as last and if dp is of size 3 i.e. till 2 index then it'll miscompute. So dp size of 4 is mandatory for first iteration in memoization.
Here's a simpler base case : if(idx
Unbelievable Content. Top notch concepts. Thanks Striver 🙏
The space optimization done in this question was amazing. Kudos to Striver.
I have no words for you! just incredible!!
In tabulation method can we just make the matrix to be n*3 and at the end find the max( dp[n-1][0], dp[n-1][1], dp[n-1][2])
yes
yp
Hey Striver,
The memoization approach doesn't work completely. it passed fo 10/11 test cases and gave stack overflow for the 11th one.
This is for Java, I even tried the solution on TUF website.
Thanks :)
any solution?
Understood, you are doing great for the community. Keep it up!😍😍
Tabulation explanation starts from 33:43
its difficult
OMG, Literally no one on RUclips is like you Bhaiya. From now onwards for DP your playlist would be referred as that for Graph. Thank you Bhaiya for heling us.
I admire your dedication striver! I wish you lot of success !!!
🤯 I must say apart from being an ace developer, you are very very skilled teacher. Teaching is not everyone's cup of tea, but you my friend can make us understand even rocket science. (Try creating its playlist as well 🤣).
can anyone give the link of similar question from leetcode
The part of Tabulation and Space Optimization were tough, thanks for the good explanation.
Hi Striver! Tried the memoization solution on codestudio. it is giving partial correct with 90% score and then runtime error for Java .
Same for mine as well bro, only 9 test cases are running out of 11
Right
Did you solve it brother?
Please let me know how you did it?
//I read the question and tried to solve it by myself and I came to this solution. (All testcases are getting passed)
#include
using namespace std;
int solve(int row, int c, int prevIndex, vector &v,vector &dp)
{
if(row==v.size()) return 0;
int maxVal=INT_MIN;
if(dp[row][prevIndex+1]!=-1) return dp[row][prevIndex+1];
for(int col=c;col
Thnxx brother, it's bcz of your effort only that i feel confident in dsa....
Understood Sir! You made it soo simple. Thank you soo much...
Understood clearly.Thank you so much for the series.
My vocabulary falls short of expressing my gratitude.. Thank you for this amazing effort.
An incredibly in-depth video. Really a MUST WATCH in my opinion. (Striver never clickbaits lol)
We can shorten the base case in Recursion and Memoization:
if(day == -1)
return 0;
This works because adding 0 to the current sum, doesn't change the sum.
bruh your level of dedication is directly reflected as our growth bruh.
Understood, Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
best video lecture in the world.
Understood!! Had to pause and think in between and replay but in the end leaves crystal clear.
Striver is just mind blowing....Thank u so much bhaiya
Understood Sir,Thank you so much for your efforts, in explaining things so easily and well enough to understand.
for the bottom-up approach, the loop: for(int last=0; last
Very good explanation. Thanks to striver.
Understood the whole video. Perfect explanation bhaiya!
But I think in tabulation line 31
At 41:00
dp[0][3] = max(points[0][0],max(points[0][1],points[0][2])
But the striver missed points[0][0] when he coded
Correct me if I am wrong!
This content is O(1) in awesomeness and O(n) in impact! Your explanations are dynamic, like an optimized algorithm! awwwwssssoooomeeee work..
Thank You so much for making these videos, it has been really helpful during placement season. The method of explanation makes it so easy to understand and grasp these concepts even thought it is my first time learning DP.
At 24:03 just wanted to make sure that 7 should be returned and not 6 from f(1,2)
ya,it will return 7
You are just amazing man!..never seen this deep and better explaination
Thank you so much Striver. Understood the 2D method.
striver is great!!!! no one can beat this approach of constructing the solution from scratch..🔥🔥🔥
Understood Striver,That was meticulous explanation 👏👏
"US"
thanks a lot striver bhau
Wow striver !!! The way you explained makes these tough concepts also easy ❤
your explanations are really outstanding
Understood very well..thanks for the amazing explanation.learnt a lot
US Thank you for these videos, your explanation is clear and helping us in understanding concepts.😊
Love you sir Amazing Explanation
thank you so much for superb level of teaching👌🙏🙏
Thank you for the very nice understanding video of dp .Really helpful ❤
Understood, lots of respect and thanks for your efforts 👏🏻👏🏻
sir, in the recursion code, actually you don't need to write another loop to get max, you can go one step behind and return 0 for that as base case, and let the recursion find last max for you.
int maxPoint(int day, int prevTask, vector &points ){
if(day
hey brother i have a doubt I have gone from index 0 to n-1
and couldnt figure out to use MEMO
It would be a great help to me if You can help to find the right appraoch
class Solution {
private:
int MaxSum (vector &arr, int i, int last_index
,vector &dp) {
//base case
if (i == arr.size())
return 0;
//recursive case
//dp part
if (last_index == -1 && dp[i][last_index] != -1)
return dp[i][last_index];
int ans = 0;
for (int j=0; j
By far hats down this is the best DP video explained intuitively. Thanks a lot, Striver.
.
BTW if you remember me, I have been your old subscriber.
.
Thanks a lot again!!!!!!
This is incredible !!! DP was a nightmare but not anymore. Thanks for this priceless material :)
Amazing Explanation Striver!! Your dedication is remarkable..
Really appreciate your efforts
Understood very good explanation thanku bhaiya
Understood bhaiya, excellent explanation!!
Haven't learned DP in a better way than this. Thankyou soo much for creating such an amazing series🤩
I need to rewatch this absolutley
understood bhaiya one of best DP playlist on entire RUclips.🙏 🙏
For tabulation, if the current tasks == 0, on day 1, DP holds the maximum possible value from the previous day, excluding task 0. That's how base cases are formed.
Understood....striver you are amazing
was able to solve upto memoization on my own thanks to previous lecture.....
US
Understood. Thank you Raj
Really Insane effort from you Striver keep up the work and understood everything
Top-notch level content
One Greedy approch will be to put all the cells value along with day and Task ( points, rowNo, ColNo) in in max heap. Also keep track of what task was greddily picked on that that day. Now when we pop an item from maxheap we do comparison with its neighbouring days
In the first eg: First we get (100, 1, 1) from max heap, daysPoints = -1| (100,1,1)
next we will get (50, 0,1) from max heap , but on checking the 0th day nbr in array: daysPoints , we find that we already did the same task. So we ignore this
next we will get (11, 1,1) from max heap , but on checking the 1st day in array: daysPoints , we find that we already slected one => ignore
next we will get (10, 0,0) from max heap , on checking the nbr on 0th day in array: daysPoints , we find that the same task was not chosen so we add it in array: (10,0,0) | (100,1,1)
Finally we sum the points.
Great effort sir. Your work is also a motivation for us.
Thank you sir 😊
Understood!
GOAT Of all Time, Your name will be remembered in past, present and future too. Hope to meet you soon buddy, as hope prevails
Helped me a lot Thank you sir
Thanks @striver for great explanation