DP 8. Grid Unique Paths | Learn Everything about DP on Grids | ALL TECHNIQUES 🔥
Lecture Notes/C++/Java Codes: takeuforward.org/data-structu...
Problem Link: bit.ly/34uoYCG
Pre-req for this Series: • Re 1. Introduction to ...
Optimal Solution using Combinatorics: • Grid Unique Paths | GO...
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we are starting with 2D DP on Grids. We solve the problem of Grid Unique paths to start with DP on Grids. I have taught this problem in-depth to understand how do we write recurrence, use memoization, write tabular DP, do space optimization.
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
Пікірлер: 1 300
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you. Wrapping the first video on a fresh topic like "DP on Grids" under 30 minutes never teaches you DP, let me write the formula and fill up the DP table. Done with DP. Here I am teaching you 4 concepts. First recursion->recursion tree->memoization->tabulation->space optimization. After this first video, the next videos will be wrapped up in lesser time as you know about DP on grids! For example, the next video wraps up in 12 minutes, the next one wraps up in 24 minutes. Its because this video is long enough to cover all concepts all at once
@riderpd09
2 жыл бұрын
Bhaiya very muchhh thank you for explaining the concepts by solving specific problems,It helpss a lot😇😇😇
@nikitaupadhyay441
2 жыл бұрын
Thank you for the wonderful content. 🥰😇
@ankit_6378
2 жыл бұрын
I watched the whole video and learnt the concept and wrote the code with memoization and Tabulation on my own (by the same approach as you explained) and both my answers were Accepted in CodeStudio, idk why your code is giving TLE.
@ankit_6378
2 жыл бұрын
Later when I saw in the end that your code is not accepted, I was surprised. lol
@AkshayKumar-oi2cu
Жыл бұрын
Sir, u r father of dp..... Thank u so much
I just wonder a man gives us such content without any money :) Here you get : 1.Basic 2.The energy in his voice 3.A good human Just Striver things .
@theishanbh
Жыл бұрын
bro he makes good money from youtube :)
@pihus3498
Жыл бұрын
But do u think he needs it when he's already working at google. Why would he do such a hectic job for himself then...making vdos at night after office. hehe.. its for us :) definitely a good person!
@pulkitaggarwal813
Жыл бұрын
so gay
@priyanshutiwari2192
11 ай бұрын
@@pihus3498 bhai kaisa hain😂
@abhinavanand1904
9 ай бұрын
Knowledge too😊😊
If anyone wondering why we didn't perform increment for each up and left like: int left = 1 + f(m,n-1); int up = 1 + f(m-1,n); return left+up; this is wrong because we are trying to find out the number of ways we can travel and not steps required to reach the destination.
@AyushPatel-fr5ni
4 күн бұрын
damn
This time I was able to write recursion + memoization by myself! Thanks a lot for this series! 😊
@lakhendrakushwah1907
2 жыл бұрын
Hi.. can you find mistek in my code #include int f(int n, int m){ if(n==0 && m==0) return 1; if(n
@mpbe
Жыл бұрын
Great
@krishanubiswas6869
10 ай бұрын
Me too.....
@JaspreetKaur-ku7pf
8 ай бұрын
that feeling is amazing
@vishious14
7 ай бұрын
Me too. I straight up modified DFS and added them to dp. 😂
Did this question all on my own. Did it by recursion first, got TLE(as expected), then used memoization and submitted the solution. space optimised with tabulation and then space optimised some more xd. Man it feels so great 😭
First of all thank you for the great playlist . This is the first playlist I'm watching in your channel. I saw chances in my code ( Dp related questions ) . Just now I attending div 2 codechef contest and I solved 4 questions , got 91 rank . The 4th question is dp , I solved that question, just 10 members solved that question when I got my solution accepted . It's still like a dream. Thanks alot Happy coding 🤗
@deepaksarvepalli2344
2 жыл бұрын
This man gave clue 😂
@Yash-uk8ib
2 жыл бұрын
@@deepaksarvepalli2344 🤣
@ChiragWadwa
7 ай бұрын
Are bhaiya aapko to Twitter par boht dekha h , cp related content daalte ho aap
@Rohinth
7 ай бұрын
@@ChiragWadwa 😃
@pain9569
10 күн бұрын
Never knew I could find Rohinth sir here. You are an Inspiration ❤️🫡
Better than Paid Course if agreed like it.
Great lecture man! I have another approach to this. assuming we have a 3*4 grid, we need to go 3 steps downwards, Let's say it DDD, and 4 steps right, Say RRRR. so if we find the number of ways to rearrange the string DDDRRRR, we get the ans. Which is (m+n)!/m!n! generally
@ashayfernandes4722
Жыл бұрын
that's a nice solution
@avicr4727
Жыл бұрын
nice approach thnx for sharing
@242deepak
Жыл бұрын
great
@nsudhir_here
Жыл бұрын
This comment should be pinned😅
@worldfromhome4033
Жыл бұрын
Yeah we used this in PNC in maths😃
For tabulation solution we can initialize for i==0 || j == 0 as 1 in base case since there is only one way to reach from (0,0) to (x,0) i.e. move x times right or (0,0) to (0,y) i.e. y times down since we can move only down/right
@amancuber5235
Жыл бұрын
Was looking for this comment
@kashishverma6397
Жыл бұрын
yeah dude you are right
@roadMapLearner
Жыл бұрын
I was looking for this comment to make sure if I didnt make the wrong understanding
Bhaiya, I have seen lots of videos on dp from youtube, udemy. And I must say, you are the best your recursion - memoization - tabulation - space optimization approach made me understand intuition behind every problem. Thanks for providing such content.
Understood. Came up with the memoization myself and was so glad when the solution beat 100% of the submissions on LC. Thank you.
This is the first time I learn space optimization in 2D dp. Thank for this awesome series.
I did it on my own....i never thought i could do this in one go. Thanks so much Striver.
@anuragpandey8165
2 жыл бұрын
Same and now its not even giving TLE for memoization soln
@DeepSingh-zs2oi
Жыл бұрын
@@anuragpandey8165 Bro it is giving TLE for memoization solution on leetcode...How have you done it?
@utkarshiitbhu4204
14 күн бұрын
@@DeepSingh-zs2oi pass dp array by reference
Hey Striver, the content is very good. FYI: you can make the base cases even simpler by taking matrices of shapes (m,0) or (0,n) into account. There is only one way to reach your destination and m and n can never go Simplest recursion would be (in python): def util(m,n): if m == 0 or n == 0 : return 1 return util(m-1,n) + util(m,n-1) return util(m-1,n-1) # One liner def util(m,n): return 1 if m == 0 or n == 0 else util(m-1,n) + util(m,n-1) # dp solution with space optimization def util2(): if m==1 or n==1: return 1 # above stated base case prev = [1]*n for i in range(1,m): curr=[0]*n curr[0]=1 for j in range(1,n) : curr[j] = prev[j]+curr[j-1] prev=curr print(curr) return curr[n-1] util2()
this is your first series that i am following and after following more than 100 lectures of another tutor I am here and literally I am feeling bad for myself why I ignored this channel since long and wasted my time. you made it easy and after following this series I am able to think about the intuition and literally earlier I was mugging up things and now I started to understand the coding stuff in better way. Thanks a lot for your efforts...
I am just amazed at how well you explain concepts! Great explanation as always! Thank you Striver!
Thanks Raj for the crisp explanation. I found this problem very easy to understand and code. I also solved UniquePaths II based on this problem with ease. I feel confident with each DP problem that I am able to solve and my fear of DP is slowly going away.
Understood the whole concept. I really appreciate your efforts striver. You make videos for us in night time with so much clarity in content. Thank you so much for your efforts and educating students like us. Thank you.
came up with recurrence and memoized soln by myself. Thank you Striver!
"UNDERSTOOD" I've solved this prblm many times before but never got this level of intuition/understanding. THANKS Striver!
i solved this question previously but the space optimization technique was just amazing ❤
Hey Striver, You just made dp so so much simpler for all of us...Thanks for all u do!!!!
I was able to solve this till memorization. The way you explained tabulation and space optimization was top notch. Thanks a ton man !!!!!!!
Thank you striver! I first wrote its code recursively and then was able to solve it by tabulation all by myself.
If u need, make more longer videos.. Don't listen to what people say.. I am with you..💚
Great series man!! I tried solving using permutation as the num of steps to right n down were fixed. So (m+n)!/m!n! Gives the result.
@takeUforward
2 жыл бұрын
Yes I mentioned this at the end!
@vamshikrishnareddy2313
2 жыл бұрын
(m+n-2)!/((m-1)!*(n-1)!) because, if You take any path, that path must contain ((m-1) Right's) and ((n-1) down's). so, we need to arrange all possibilities.
You're the best. I love the space optimisation part, your flow of solutions is amazing!!!!
Everyone are talking about striver writing base cases in tabulation and space optimization instead of declaring them i agree it makes it lengthy but he just wanted to make us understand how to use recursion code while writing them , you can make it short when you know the constrains like i did below . vectordp(n,0); dp[0]=1; for(int i=0;i
don't know if m gonna be happy or sad if by any chance my interviewer turns out to be striver 😂
dp[lect 8]=dp[lect (8-(0 to 7))]+understood;
@SahilKumar-lq5rj
2 жыл бұрын
op
I'm now able to solve dp problem. Thank striver for the immense work you have done for everyone.
I never thought that i could solve problems on paths. I am really enjoying this series. 🥰
I will start watching 😂, In advance understood
Understood! Thank you so much for your explanation of the concept!!!
I have watched a lot of DP videos but this on some next level great explanation in detail.
sir, i was regularly watching atleast one video and today i was in a position where before you tell the recursive way i was able to write it and code it as well. Thank you for explaning these problems soo well 🔥🔥
Didn't understood space optimization in one go, was disappointed then came back again to watch and now I can say UNDERSTOOD🌻Thankyou Striver!♥♥
I am able to do this question just as you did without looking the code. This is because how you taught the dp in the first few questions. I am able to do all the solutions for this question just as you did. Thank u Striver.
have understood nicely ! all the 3 methods
I was able to solve the memoization and tabulation myself and the code was exactly same as yours . Thank you Striver. Understood
UNDERSTOOD.......Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
great playlist. Very easy to understand
Understood. Very nicely explained all approaches and further space optimization. Thanks for making such wonderful videos.
able to solve question by myself loving this series thank you so much striver
Fully understood, awesome lecture!!!!
UNDERSTOOD!? Nah bro youre a G - O - D. Nothing less than a God for IT Students. The way you explain such complex problems, and that too on platform like YT! For completely free, while there are so many guys doing it for thousands of Rupees and still not delivering such content as yours, I can do nothing but bow in front of you RAJ SIR. May god give you and your family every happiness. Thank you so much.
@user-rn7bs9ou6u
5 ай бұрын
bhai placement lag gaya?
So beautiful, so elegant. Just looking like a WoW❤🤩😍Thanks striver bro.
Very well explained understood better than ever
I solved it in just 15 mins without watching your solution. I am very happy. You are amazing Striver. Keep up the good work. And yeah as always thank you so much :)
Great explanation, thank you.
Hey Striver, i was able to solve this problem by my own, key is to write recurrence relation starting from m-1,n-1 indexes. Thanks bhaiyan for your unbeatable DP series.
I learned space optimization before but I didn't always use it because I didn't practice it enough. But after watching some many of your videos, it now second nature to me.
Understood... really amazing way of teaching
Upto now whatever u taught is awesome like I can't express how efficiently u taught us... Thanku so much..
your explanation of the questions explains us depth of your knowledege about dp.
Thanku for making DP so easy stiver and now they fix the error i submitted answer with all 3 approach.
I am able to write recusion, memoization and tabulation solution without looking at the video and took me around 1 hour. Thanks for making DP easy.
I think this is how DP should be taught. Other people start with tabulation and stuff but a beginner (like me) needs a simple yet precise explanation of tabulation , memoization and recursion which this video delivers in a very excellent way. If this were a paid course, It would be insanely famous, (just like now)
Understood. Thank you Sir
much easier to understand and very short code: int uniquePaths(int m, int n){ vector dp(n, 1); for(int i=1;i
I actually thought of this recursive solution but wasn't sure that it is gonna work and was probably too scared to try it out so again watched your awesome video. Great Teaching skills....
Thanks Striver for making such a difficult topic so easy to understand.
46:33 Bhaiya we can also do it with a single vector int uniquePaths(int m , int n) { vector prev(n,1); for(int i=1 ; i
just understanded the question and stoped 6:23 then did all the 4 solution on my own. very happy
I was able to solve this question by myself just coz I had done recursion from Striver's playlist. Thank you so much :)
Understood. Thanks for creating the playlist.
Understood ! Thanks ✅✅
Understood it clearly. Thank you so much:)
This time i wrote space optimisation myself 😁.Thank you striver ❤
This dp series was simply superb,and I understood very well
Understood. Your explaination are so on point and are soo easy to understand.
class Solution { public: int uniquePaths(int m, int n) { vector arr(n, 1); for(int i=1; i
Thanks a lot man !!! 🙌🙌
Thank you sir 🙏 Understood...
Excellent content.!!!!
understood, Thanks
OP Explanation!! Understood
Thanks for the effort❤️🔥. We appreciate your help and the hard work.
tysm striver bro. 😍
one of the best dp series
thankyou strver for the lectures i was able to do this
thanks to you @takeUforward i have solved this problem without seeing your video
Understood, The space optimization part was explained very nicely.
after space optimization , it literally makes the code of four lines :) amazing tutorial, us, us, us. thanks a lot
Thanks Understood
I am coding in Java but to understand the logic I come here on your channel....Thanks bhaiya
Great Video as usual and good series, with the start of 2D dp and last question, I thought it will be tough but as I see it's not as much.
Thankyou so much striver for amazing content
I understood this one perfectly. Thanks a lot man
Loved this Lecture of yours, Understood 🔥🔥🔥
understood bro, thanks a lot for the effort, you are making a huge impact , keep going
best explanation Thank you striver
yes i'm "understood " because your teaching level is very very good thanks bhaiya❣
Very well understood
Understood Striver!!! thank youu;)
understood very well
Just wowww!!! level of explanation.... understood
Yes... I did understood. thanks.
understood crystal clearly in one go.. amazing explanation..
Man you are going to be something...just keep it up!