DP 2. Climbing Stairs | Learn How to Write 1D Recurrence Relations

Подписаться 610 тыс.

Просмотров 427 тыс.

50% 1

Lecture Note: takeuforward.org/data-structu...
Problem Link: bit.ly/3t1Sjyx
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Pre-req for this Series: • Re 1. Introduction to ...
Full Playlist: • Striver's Dynamic Prog...
In this video, we have discussed how to write recurrence relations using the problem of climbing stairs. I have told you three important points which can help you in writing any recurrence relations.
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

Опубликовано:

15 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 947

@utkarshyadav3401 2 года назад

You say consistency !!! I hear Striver !!!! 😊😊😊 Man you are too good !!!!

@MadhavGupta-fi2tu Год назад

Points to remember: Step1. Identify a DP Problem. Step2. To solve the problem after identification. 1. Try to represent the given problem in terms of index. 2. Do all possible operations on that index according to the problem statement. 3. To count all possible ways - sum of all stuff. To find minimum/maximum - Take Minimum/maximum of all stuff. Understood 🔥🔥🔥

@niteshsaxena1066 2 месяца назад

These steps will work well on leetcode/GFG but not on codeforces For CP, you need to watch priyansh video

@user-bo9br3bo4y 8 месяцев назад

I finished my engineering and now I m working , came back to listen to the song that gets played for few seconds in last . Good old days.

@nikhilgupta2569 Год назад

Great work Striver. Just couple of observations since f(n) denotes no of ways to reach nth stair from step 0. It implies f(0) should be 0(you don't have to move at all, you are already at your destination), f(1)=1(because only one step of single jump needed) and f(2) = 2 because in this case either two times a 1-step can be taken or a single 2-step works. So closely this pattern doesn't resemble fibonacci till index 2, because f(2) is not a sum of f(1) and f(0), rather they are adding upto 1. So my logic would be: // JS Snippet const climbStairs = function(n) { const recursion = (i) => { if(i

@vamshisamsetty186 Год назад

Was thinking the same!!

@MP-eq8fx Год назад

Thank you Nikhil. You explained it very easily. So I wrote it this way: //JS Snippet function numOfStairs(n) { if (n

@sahillodha6084 Год назад

Firstly I thought that at f(0) he can't move and over there return 1 indicates that even not moving can be considered as a way but it will be same for entire problem and make it unsolvable but it isn't so you have cleared thank you

@aasifali9139 Год назад

I was thinking the same.. that why is there 1 ways to reach stair 0?

@TIMEe.. Год назад

Your code will fail for 3

@keshav_k_0793 Год назад

1. Try to represent any problems in terms of index 2. Do all possible stuffs on that index, according to the problem statement 3. Sum of all stuffs ->count all the ways , min(of all stuffs) -> Find min

@utkarshaggarwal1631 Год назад

I understood this as : to reach the nth stair, you find out the ways to reach the (n-1)th stair (from where you take 1 step to reach nth stair) and the ways to reach the (n-2)th stair (from where you take 2 steps to reach the nth stair), and sum them to get total no. of ways. Is my understanding correct?

@AbdulRahman-tj3wc Год назад

Absolutely correct

@GurpreetSingh-ou4wj 2 года назад

Understood! earlier was doing it in another way, but today i got a new way of thinking i.e. if we are on nth idx then we have jumped from n-1th and n-2th 🙃

@sukhpreetsingh5200 Год назад

Understood! I done this question myself thanks a lot to u for this amazing series

@syedakhudsiyatarannum5695 Год назад

understood solved the problem on my own just after reading the question thanks to your recursion playlist and 1st video on dp

@manantyagi6905 Год назад

Bestest stuff of all the cases of tutorials on youtube

@stith_pragya 6 месяцев назад

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

@DebojotyRudra 2 года назад

Finally after 7 month because of you bhaiya got to know the intuition behind aolving a DP problem and the patterns too.....fully understood

@dpxy1599 2 года назад

Yess

@dharmeshpoladiya9047 2 года назад

Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥

@vishalchoudhary5918 2 года назад

I struggled hard to get its recursive bit u made it so much easy

@tanishamajumdar3552 Год назад

points to remember any problem should be broken down to a recursive function. 1. try indexing 2.try writing all possibilities using indexes 3.for finding min /max => count the no. of ways(sum of all f(n))=>min/max(all posssible f(n))

@atech_guide 2 года назад

Great Explaination in building the recursion. Thanks

@lakshmichandhana Год назад

Amazing Lectures ,learnt a lot .Great initiative.

@shuvbhowmickbestin 11 месяцев назад

Hi striver, if you're reading this then I'd request you to put this video in the shortened version of this playlist as well since here you're teaching how to encounter problems related to 1D array which is necessary to understand to be able to solve 1D problems on DP.

@Sanya-ic8gr Месяц назад

UNDERSTOOD! Thank you striver!!

@rashmikareddy3259 2 года назад

Learning to be consistent from you sir.. UNDERSTOOD

@alienx2367 2 года назад

Just a suggestion you can cover whole screen by the black board, just a small rectangule for your face at left or right bottom

@takeUforward 2 года назад

The iPad screen reso is small. So if I elongate it to the whole screen, it stretches and the colors go off.

@rabindrakumar949 2 года назад

Face is not required.

@takeUforward 2 года назад

Padhai kar lo, face rhe na rhe usse kya h. 😂

@ManishKumar-qx1kh 2 года назад

@@rabindrakumar949 why r u focusing on the face, just get the knowledge he is sharing for free.

@rabindrakumar949 2 года назад

@@ManishKumar-qx1kh I am not able to focus most of the time on actual content due to the face. In Aditya Verma video I like the fully content screen. And about free content, yes we get the content as free and do you think someone in this world will work to provide such valuable content without getting paid. I guess some indirect money must motivating them to provide such incredible content.

@yt_ac 8 месяцев назад

Day - 1 : understood the three points clearly

@ekta9145 29 дней назад

Understood! Thank you very much, sir.

@RAHULKUMAR-sx8ui 2 года назад

if logic is magic then you are a great magician appreciate it sir ❤️

@lifehustlers164 4 месяца назад

3/57 done!!! Understood!

@atharvakalele37 2 года назад

Do I just need to solve these questions first before attempting anything similar on leetcode or do I need to do both leetcode and your problems both on parallel....btw you are the best teacher I ever learned from...keep on making these videos man...and education would become completely free soon!

@likhitbhogadi 7 месяцев назад

thanks bro, understood..

@easycode3189 Год назад

nderstood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥

@sakshiupadhyay3284 2 года назад

More power to you striver... "UNDERSTOOD"

@VivekJaviya 2 года назад

Leetcode daily problem + Codechef daily problem + GFG daily Problem + Striver Daily dp problem = :)

@sakthi6023 Год назад

=Google

@kingmaker9082 Год назад

So, ur planning to become SDE in Meta 🤙

@VivekJaviya Год назад

@@kingmaker9082 Meta to nhi but USA ke startup or MNC se offer to mil gaye upar ki chijo se!

@kingmaker9082 Год назад

@@VivekJaviya bro iam also preparing in the same pattern nd I'm currently studying mca 1st year. Iam looking for ppo's in mncs like Goldmansachs, Amazon, uber etc...could you plz say ur linkedin id?

@Harshanandita Год назад

Are you saying practicing every day or are you talking about the problem which is given everyday on LeetCode and GfG?

@lavakumar3243 10 месяцев назад

The first thought It came to my mind was permutation and approached like permutation with repetition, but it gave timeout for test cases after n=30.

@ganapathyg981 2 года назад

Thanks for explaining in English.. love from Tamilnadu 😎

@newtonsir6752 2 года назад

I'm ur new subscribers. Thank u for all the efforts and please continue to do so. Ur lectures are great. Please explain me the base case : Why return 1 ?

@dhrubajyoti3774 2 года назад

Bcoz there is only one way to reach step 1 from step 0

@vikasbagri1225 2 года назад

you can think (n == 0) as you have ultimately reached to your destination i.e. at the nth step and no need to take any more step and thus you can conclude that you have found one of the way to reach the nth stair and hence return 1 indicating that hey I have found one of the possible way to reach the target and you can actually increment the total count of possible ways to reach the nth stair I hope it helps

@gurveer1527 2 года назад

int countDistinctWays(int nStairs) { //DP Tabulation solution int mod = 1000000007; vectorDP(nStairs+2, -1); //Initial Steps DP[0] = 1; DP[1] = 1; for(int i= 2; i

@shreyanshgupta6163 Год назад

Why you took nstairs+ 2 istead off nstairs +1?

@ranjannitjsr533 11 месяцев назад

@@shreyanshgupta6163it should be n+1

@AyushRaj-sx6ju 2 года назад

Kudos to your effort striver ❣

@nimsguy Год назад

Thanks for the explanation and whole series!. Shouldn't base case be if(index === 0) return 0 ?. If this is right, then when n=3, we will have only 2 possible ways to reach step 3 which is incorrect ?.

@karansumbly1254 11 месяцев назад

We are not counting the number of steps but the number of ways. So as soon as the function hits 0, we can say that we have found a new way and hence return 1.

@sakshisinghal1669 2 года назад

I am unable to understand why we need 1 to jump to same stair that is from 0->0 (base case)? According to me it should be zero. Correct me if I am wrong.

@sandeepdeepu5052 Год назад

I too didn't understood in the beginning but after sometime I figured out that = see you are coming from n to reach 0 which means there is way from n to our destination '0' so you return 1 saying that there is a possible way from n to reach 0 so it is returning true. You should not think like from 0 to 0 there is no way then why i am returning 1. You have think from the given "n' perspective. because 0 is the last index to get on so if we get to the last index we found out a way from n. So when we reach to 0 index we are saying to n that " hello n there is a possible path from u".

@kaushikmahanta6463 Год назад

@@sandeepdeepu5052 thank u

@sandeepdeepu5052 Год назад

@@kaushikmahanta6463 felt happy that you understood my explanation.

@somnathroy102 Год назад

This is so simple. Thank you Understood.

@perveenneha1423 2 года назад

understood heart felt thank you

@punitgarg4627 2 года назад

one small mistake ,for idx==1, return 1 aayega instead of 0, nicee explanation sir❤❤

@035asadali8 2 года назад

he mentioned in video ,u missed

@ketanahuja8939 2 года назад

At 7:25 , it will be return 0 when (ind==0)

@shreyanshpatil8303 2 года назад

no it will be 1

@siddharthb2226 2 года назад

yaara ne

@ratinderpalsingh5909 2 года назад

Understood, sir. Thank you very much.

@shivammishra2413 22 дня назад

understod.thanks striver bhaiya ❤

@karanjitsinghrandhawa445 2 года назад

Bhaiya I am currently learning c++ by this month I will complete all fundamentals of c++ Please bhaiya can you suggest me where to start DSA as a beginner ????? Please bhaiya reply Love from Guwahati ❤️

@AbhishekSingh-kt8fi 2 года назад

For DSA in cpp check out dsa playlist from simple snippet!

@harshitparashar 2 года назад

Abdul bari

@karanjitsinghrandhawa445 2 года назад

@@AbhishekSingh-kt8fiso means after c++ i can start with simple snippet???

@karanjitsinghrandhawa445 2 года назад

@@harshitparashar for beginners will it be good???

@harshitparashar 2 года назад

@@karanjitsinghrandhawa445 yup

@devanshkumar3816 2 года назад

understood! but one confusion... shouldn't it be "if(ind == 0) return 0; " as we are left with no way to reach to the end when ind equals 0 !

@rohalkurup1350 2 года назад

remember as if for standing in the same place there is one way , logically speaking there is no way , but if we are considering the problem here it will be 1

@suhailansari3847 2 года назад

@@rohalkurup1350 how 1?

@akshaydeshmukh5390 2 года назад

You are right. It should be 0 as we have already reached the destination and don't need to move any further. You can write separate base case like if (index

@nimsguy Год назад

@@rohalkurup1350 but is it kind of confusing ?. because at step 1, yes there is one way to reach step 0, but at step 0, there is no way to reach as it is already reached. bit confusing this part is. :-(

@poisegaming2448 Год назад

class Solution { public int climbStairs(int n) { int prev2 = 1; int prev1 = 1; for(int i =2;i

@shivanshumishra0560 Год назад

Understood !!! really awesome explaination........

@aagamjain2131 Год назад

Awesome explanation!! Understood sir 🔥💯

@suryashjha7892 2 года назад

Amazing explanation 🔥🔥🔥

@avtarchandra2407 2 года назад

Kudos to your effort striver ❣️

@AnitaSharma-bk4fc 7 дней назад

Understood thanks striver❤

@SwapnilChavan-im7xh Год назад

Understood 🔥🔥🔥 Thanks for Your teachings

@codecrafts5263 2 месяца назад

Tabulated solution: function f(n){ if(n

@desihiphop4998 2 года назад

Understood !!!!!!!! Fully sasfied !!!!!!!

@thenriquevicentini 3 месяца назад

Understood, thanks!

@NazeerBashaShaik 7 месяцев назад

Thank you!

@vakhariyajay2224 Год назад

Thank you very much. You are a genius.

@ritikasingh7252 2 года назад

Awesome explanation👏

@amalasebastian9968 11 месяцев назад

Liked the video even before starting it..Obviously its made by Striver ,it had to be great❤

@user-ym1nv1pw8i 28 дней назад

Understood! Mark for revision!

@prathyushabuddarapu314 2 года назад

UNDERSTOOD SIR...! Thank you

@tango2olo Год назад

From step N-1 there is only 1 way to reach Nth step i.e. a 1-step jump. But from step N-2 there are 2 ways to reach step N, 2 1-step Jump and 1 2-step jump. So the recursion shall be Sol(N) = [Sol(N-1)*1] + [Sol(N-2)*2]; because for each Sol(N-2) we have 2 ways to reach Sol(N).

@komalkrishna7836 2 года назад

Understood... Thank you!

@amitpawar8035 2 года назад

Awesome explanation as always

@rahulreddy3588 11 месяцев назад

Understood very well!👌

@creativeprojects217 5 месяцев назад

thank you sir❣

@addityasharma6426 2 года назад

understood, great explanation bhaiya😊😊😊

@insofcury 2 года назад

Represent the problem in index format Do all possible operations on the index do count or find min/max Understood!

@Shivi32590 13 дней назад

thank you

@raghavmanish24 Месяц назад

uunderstood.....thanku striver

@nithishlelll9664 7 месяцев назад

understood!😇

@user-ym1nv1pw8i 27 дней назад

Here's the c++ code which I submitted (For reference): int f(int n, vector &dp){ if(n

@deepakabari17 Год назад

Very well understood 👏👏

@priyatamkumar518 2 года назад

understood , a lot of wishes for you

@siddheshborse3536 Год назад

Not getting feeling of Solution.... but understood the shortcut very well... thank you😀

@dheerajshukla7008 Месяц назад

understood bhaiya

@chahakjain6787 Год назад

very easy explanation sir!!

@drishtirai864 5 месяцев назад

Understood ..!!

@jayantmishra6897 Год назад

bhayia your way of teaching is amazing.one thing i want to ask you that from where did you learned all these.

@natashadale6333 2 года назад

Good job 💙🌼

@DPCODE72 2 года назад

Now I would believe in myself that I will be selected as A SDE in Amazon soon. Bhaiya with ur support & help.

@aditianand6966 10 месяцев назад

thank you for making such a good content

@akshitmangotra5370 Год назад

understood! Thanks!!

@ratnak5370 2 года назад

FULLY UNDERSTOOD

@rtadwq...------...----. 2 года назад

Nicely explained sir

@Aladin40chor 8 месяцев назад

Understood ❤👑

@arihantjammar8888 9 месяцев назад

Understood 😊

@BhavyaJain-qz8jg 7 месяцев назад

understood👍👍

@programmertik2046 2 года назад

int ways(int i,int n, vector&dp){ if(dp[i]!=-1){ return dp[i]; } if(i==n){ return 1; } if(i>n){ return 0; } return dp[i]=ways(i+1,n,dp)+ways(i+2,n,dp); } Why this gives heap buffer exceeded and why we go from n to 0 when we go can go from 0 to n