DP 7. Ninja's Training | MUST WATCH for 2D CONCEPTS 🔥 | Vacation | Atcoder | 2D DP |

Lecture Notes/C++/Java Codes: takeuforward.o...
Problem Link: bit.ly/3F4yl8z
Pre-req for this Series: • Re 1. Introduction to ...
Make sure to join our telegram group for discussions: linktr.ee/take...
Full Playlist: • Striver's Dynamic Prog...
In this video, we are starting with 2D DP. We solve the problem Ninja's Training which teaches you how to think of other parameters apart from index. We also learn space optimization in 2D 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...

[@takeUforward]

I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.

[@akshayrawal3853]

make a video on time and space complexity from basics to advanced

[@Zunan263]

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

[@takeUforward]

@SACHIN SHARMA everyone will have a different thought process, there is no hard and fast rule for base cases!

[@dhanshreebornak8486]

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.

[@virendrakhanduri4897]

"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.

[@ankitadas5833]

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]

❤️

[@asutoshghanto3419]

@@takeUforward when do you sleep then ?

[@yyvaibhav]

@@asutoshghanto3419 maybe he recorded on weekends

[@shlokhinge3179]

@@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

[@anonymousvoid6356]

This man is insane

[@riteshbisht94]

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 🔥🥳

[@rushidesai2836]

That's correct. He's recording this at late night. That's why.

[@imPriyansh77]

thanks

[@rocketscience800]

yeah that's right 7 for a reason....

[@ashishkumar-px5dh]

yeah i checked that and immediately come top comment to comment sectiona nd i found you

[@manivelnagarajan5396]

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🙏

[@sarangs722]

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.

[@reenachandarana4459]

Hi Striver, This was the very first time I approached a 2D DP problem, and I tried to solve it by myself initially and I was able to solve it within 30 minutes. All credits to you man, I have been following the A2Z DSA sheet and it has improved by coding skills to next level and the way of approaching the problem. Lastly, thanks for making such a wonderful content and no words can explain how much I enjoy learning through your videos. Keep growing.

[@gyanunlimited740]

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!

[@nidhishprasad2506]

did you?

[@gyanunlimited740]

@@nidhishprasad2506 U doubt?

[@nidhishprasad2506]

@@gyanunlimited740 No, it's great. I was asking you if you are able to solve dp problems now?

[@gyanunlimited740]

@@nidhishprasad2506 Better than ever before

[@bluesteel1]

im also 25 and learning dp

[@sumitvishwkarma6907]

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.

[@iamnoob7593]

indeed!

[@himadrinath1502]

This question is quite hard.

[@rishitsrivastava3070]

28:18 love how his declaration coincided with the lights going out. Thanks for the content as always

[@VarshaSingh-hi2sb]

Why dp array is declared with size 4? And how the time complexity is O(N*4)*3?

[@pratyushbhatt1712]

@@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.

[@VinayKumar-xs6el]

@@VarshaSingh-hi2sb dp array size depends on input array size u can take same as input

[@himanshubarak3528]

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.

[@sayansadhukhan9692]

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.

[@shaurydeep]

right, i also got stuck there, after some time I get it little clear in my mind.

[@nirbhay0799]

it took me as much time to understand the tabulation as it did not take me time to understand the entire video.😪😪

[@mayanksaurabhmayanksaurabh9271]

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.

[@spiral546]

@@mayanksaurabhmayanksaurabh9271 did you got that??

[@Neeraj-jz6eg]

No one teach space optimization. I learn space optimization by watching your videos. Thank you so much for providing this course.

[@foziezzz1250]

Beautifully explained! After many years of avoiding dynamic programming (DP), finally discovering this playlist during my first proper attempt at learning DP feels like an indescribable blessing.

[@shamikbhattacharjee7321]

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.

[@Aladin40chor]

Exactly it should be 7

[@TheSketchbookSessions.656]

Yaa that should be 7@@Aladin40chor

[@antibarcelona2123]

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

[@asmitraj4740]

Yeah bro it must be 7.

[@rushhour4379]

@@antibarcelona2123 the max returned would be 14 and not 12. max((8+1), (7+6)). So it does make a difference

[@bhanujuneja58]

us. What an explanation from memoization -> tabulation -> space optimisation. Terrific and totally unique. Thanks Striver.

[@parthsalat]

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.

[@DeepakBhallavi-i3o]

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

[@abhayurmaliya6801]

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 !!!!

[@manikantasai6118]

That striver on hand at 26:50 was literally 🔥

[@jigyansoo]

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.

[@skiver9763]

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.

[@takeUforward]

Thankyou for commenting so late at night.

[@redfinance3403]

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 😃

[@tanishqtyagi1465]

His level of teaching is incomparable !!

[@gaurabdas1510]

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! 👌🔥

[@parthsalat]

Exactly! I had the same thought!

[@calmyourmind5617]

Yes right. I noticed it also.. Thanks for pointing out.

[@venkateshnagumantri3130]

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.

[@subhambhakat3908]

@Gaurab Das.Can u explain how??

[@chamanjain9843]

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]); }

[@spandanrastogi7144]

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.

[@KedarBhawthankar]

yes

[@lakshmand8413]

What an explanation from memoization -> tabulation -> space optimization woww Terrific

[@killua8762]

in the top down approach, i feel instead of writing that much code for day==0 case we can just return 0 for day

[@rohitchanda8461]

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 ❤

[@priyamshankar468]

100%

[@rydham8252]

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.

[@veda615]

"Us", the best video on DP, nobody I say nobody could explain like you did, Thanks alot.

[@MohithKumar-46]

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!

[@tej.askamble]

you are correct.. but idk how it gives correct solution

[@ankurprabhu2547]

sir at 24:04 it should return 7 right and not 6 . btw thankyou for your efforts us !! .

[@SanjeevKumar-kg3yu]

Ri8

[@EditorGuru]

Yes

[@kartik_265]

Yes , because f(i,j) means , maximum points on day i when previously task j was done.

[@akshayrahangdale8511]

i was gonna point it but thanks

[@Rajat_maurya]

yeah

[@ntgrn-pr5yx]

understood , you are a gem dude , UNIVERSE IS WITH YOU

[@shubhanshukumarsingh6133]

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.

[@sumitsoni2713]

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]

@@sumitsoni2713 oh got it

[@sumitsoni7559]

@@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]

but it is running without making that. u were correct, its extra effort only. we only require valid index

[@googlewasmyidea9895]

@@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.

[@pravinmudaliyar3421]

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)); }

[@swastikdey1800]

Never thought dp could be this fun. I am grateful to you sir.

[@Ani_86_]

is there a small mistake at 24:01 ...we should go with 7 instead of 6 right ??

[@VIVardhan5130]

Yes we should get 7 as max but mistakenly wrote 6..

[@siddhantchourasia291]

Unbelievable Content. Top notch concepts. Thanks Striver 🙏

[@rrpo6327]

the best teacher in dsa ... want like these contents in java completely

[@vikashprajapati8077]

good series, just after 6 lectures, I was able to do this question on my own.

[@gautham227]

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])

[@indraneelghosh2923]

yes

[@ayushmanshivhare2902]

yp

[@nihalrawat1431]

Here's a simpler base case : if(idx

[@UR_spongebob]

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

[@sudhanshukushwaha6351]

correct was thinking the same why not keep in variables instead of array

[@clashtm8210]

same thing i guess. won't change the complexity of O(4). Cause you are essentially using 4 variables

[@mohammadahsan7873]

The space optimization done in this question was amazing. Kudos to Striver.

[@threemusketeerscalypso2099]

Thanks a lot striver.Just by reading question I was able to solve it.Came back to your video just to reinforce the learning .

[@nitunsingh6986]

OMG, Literally no one on KZbin is like you Bhaiya. From now onwards for DP your playlist would be referred as that for Graph. Thank you Bhaiya for heling us.

[@parthsalat]

Tabulation explanation starts from 33:43

[@sageoustheory1957]

its difficult

[@amanasrani6405]

Understand Bhaiya, You are really Amazing Hats off to your Hardwork Because of Your Hardwork most of us are getting Placed Really Grateful

[@rizwan-io]

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 :)

[@kermitdaphrogge525]

any solution?

[@divyanshuagarwal3111]

yes..same problem encounters with me

[@sudhanshutiwari7089]

🤯 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 🤣).

[@sahiltomar5767]

An incredibly in-depth video. Really a MUST WATCH in my opinion. (Striver never clickbaits lol)

[@thats_so_pranav]

Hi Striver! Tried the memoization solution on codestudio. it is giving partial correct with 90% score and then runtime error for Java .

[@muditagrawal7357]

Same for mine as well bro, only 9 test cases are running out of 11

[@binitakumari2080]

Right

[@anishali8042]

Did you solve it brother?

[@anishali8042]

Please let me know how you did it?

[@suryadiproy7603]

can anyone give the link of similar question from leetcode

[@shubhankarnikam-x9g]

understood properly and process of recursion to space optimization is amazing ❤

[@amanwarudkar9913]

//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

[@mukitmahmudul2616]

My vocabulary falls short of expressing my gratitude.. Thank you for this amazing effort.

[@nishitar3915]

You are simply Commendable Striver!!! Always grateful to you!!!

[@SelvaArumugam-xq5mf]

bruh your level of dedication is directly reflected as our growth bruh.

[@tarunsingh2480]

your explanations are really outstanding

[@jabedhasan21]

Understood, you are doing great for the community. Keep it up!😍😍

[@inshafatma3406]

Striver you are great ❤

[@vanshnawander1615]

I have no words for you! just incredible!!

[@sairajrajput4857]

best video lecture in the world.

[@ComplexConqueror]

Understood clearly.Thank you so much for the series.

[@PapaMomarNokho]

I admire your dedication striver! I wish you lot of success !!!

[@sandipanadhikary5546]

Thnxx brother, it's bcz of your effort only that i feel confident in dsa....

[@anupriyagola5838]

This is incredible !!! DP was a nightmare but not anymore. Thanks for this priceless material :)

[@shriRadheHariom]

Understood Sir,Thank you so much for your efforts, in explaining things so easily and well enough to understand.

[@stith_pragya]

Understood, Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@kavishmehta6094]

You are just amazing man!..never seen this deep and better explaination

[@azurefrost8967]

Understood sir, thank you so much for your hard work

[@RituKumari-hx5on]

Understood Sir! You made it soo simple. Thank you soo much...

[@sangharshpipare666]

The part of Tabulation and Space Optimization were tough, thanks for the good explanation.

[@gautammali768]

Striver is just mind blowing....Thank u so much bhaiya

[@toletijayasri6540]

US Thank you for these videos, your explanation is clear and helping us in understanding concepts.😊

[@kunjgupta1258]

Understood! Love you❤

[@ToonDubberDuo]

i watched the 10 mins, learnt the keeping track of last day intuition, wrote the memo code and won't proceed to do tabulation and space optimization because i don't want to ^_^

[@bhanupratapsingh7135]

Understood the whole video. Perfect explanation bhaiya!

[@deepakdas4513]

best explanation by far 👍

[@arihantjain9496]

Top-notch level content

[@DurgaSarvaniAnkala]

Wow striver !!! The way you explained makes these tough concepts also easy ❤

[@Adib-ti2mw]

Understood sir. Amazing explanation.

[@manasansh7198]

Really Insane effort from you Striver keep up the work and understood everything

[@technojam5944]

06:33 Ninja's Training 2D DP 10 day schedule 13:06 Utilizing previous task information in recursion for task selection 19:39 Optimizing task performance by avoiding repeating tasks on consecutive days 26:12 Understanding recursion and overlapping subproblems in dynamic programming. 32:45 Understanding the parameters and concepts of 2D dynamic programming 39:18 Tabulation method for optimizing time and space complexity explained 45:51 Tabulation is an efficient method for dynamic programming 52:18 Optimizing space complexity for DP problems by reducing memory usage.

[@ginnijain5859]

commendable explanation striver 🥇🥇🥇🥇🥇

[@aakashshivanshu3578]

Thank you so much Striver. Understood the 2D method.

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@suyashkejriwal5794]

Understood, lots of respect and thanks for your efforts 👏🏻👏🏻

[@anmol3749]

Understood Thank you striver🙌🙌

[@aruncp9374]

Thank you for the very nice understanding video of dp .Really helpful ❤

[@sainisaab8539]

UnderStand in O(1)

[@AyushNitkkr89]

Understood Sir ❤❤😍😍

[@averylazyandweirdhuman]

Amazing Explanation Striver!! Your dedication is remarkable..

[@vibhavsharma2724]

Very good explanation. Thanks to striver.

[@UECAshutoshKumar]

Thank you sir 😊 Understood!

[@singh.guransh]

Great video sir 🫡

[@keshavbadhekar]

49:18, why did he replace dp[day][last] with temp[last] and not with temp[day]? Think about it this way: if you extract a single row from a 2D array, you will traverse it column-wise, right? That’s why he kept the column index and removed the row index. I know it’s obvious, but sometimes people like me don't immediately get this kind of stuff. Just trying to help out people like me... haha!

[@sanyamjain1053]

#understood amazing series with every video i am learning many new concepts can't get these things in paid courses

[@user-bt6mh9ez3u]

Understood very well..thanks for the amazing explanation.learnt a lot

[@shivaanikrishnakumar497]

Understood crystal clearly, DP used to be like an alien concept to me. It's not anymore !!! :)

[@sagnikadhikary5210]

Great effort sir. Your work is also a motivation for us.

[@shubhammurarka6589]

was able to solve upto memoization on my own thanks to previous lecture..... US

[@BiswajitDas-lk7pp]

Love you sir Amazing Explanation