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

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

[@utkarshyadav3401]

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

[@user-bo9br3bo4y]

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.

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

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

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

[@TravelTracksByDebo]

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]

Yess

[@manantyagi6905]

Bestest stuff of all the cases of tutorials on youtube

[@syedakhudsiyatarannum5695]

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

[@GurpreetSingh-ou4wj]

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

[@dharmeshpoladiya9047]

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

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

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

[@stith_pragya]

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

[@vishalchoudhary5918]

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

[@shuvbhowmickbestin]

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

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

[@rashmikareddy3259]

Learning to be consistent from you sir.. UNDERSTOOD

[@atech_guide]

Great Explaination in building the recursion. Thanks

[@lakshmichandhana]

Amazing Lectures ,learnt a lot .Great initiative.

[@RAHULKUMAR-sx8ui]

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

[@atharvakalele37]

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!

[@sakshiupadhyay3284]

More power to you striver... "UNDERSTOOD"

[@ekta9145]

Understood! Thank you very much, sir.

[@yt_ac]

Day - 1 : understood the three points clearly

[@lifehustlers164]

3/57 done!!! Understood!

[@easycode3189]

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

[@alienx2367]

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]

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

[@rabindrakumar949]

Face is not required.

[@takeUforward]

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

[@ManishKumar-qx1kh]

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

[@rabindrakumar949]

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

[@VivekJaviya]

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?

[@newtonsir6752]

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]

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

[@vikasbagri1225]

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

[@somnathroy102]

This is so simple. Thank you Understood.

[@ganapathyg981]

Thanks for explaining in English.. love from Tamilnadu 😎

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

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]

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.

[@AyushRaj-sx6ju]

Kudos to your effort striver ❣

[@gurveer1527]

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]

​@@shreyanshgupta6163it should be n+1

[@punitgarg4627]

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

[@035asadali8]

he mentioned in video ,u missed

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@lavakumar3243]

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.

[@ketanahuja8939]

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

[@shreyanshpatil8303]

no it will be 1

[@siddharthb2226]

yaara ne

[@karanjitsinghrandhawa445]

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]

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

[@harshitparashar]

Abdul bari

[@karanjitsinghrandhawa445]

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

[@karanjitsinghrandhawa445]

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

[@harshitparashar]

@@karanjitsinghrandhawa445 yup

[@likhitbhogadi]

thanks bro, understood..

[@aagamjain2131]

Awesome explanation!! Understood sir 🔥💯

[@devanshkumar3816]

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]

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]

@@rohalkurup1350 how 1?

[@akshaydeshmukh5390]

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. :-(

[@avtarchandra2407]

Kudos to your effort striver ❣️

[@shivammishra2413]

understod.thanks striver bhaiya ❤

[@shivanshumishra0560]

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

[@perveenneha1423]

understood heart felt thank you

[@prathyushabuddarapu314]

UNDERSTOOD SIR...! Thank you

[@SwapnilChavan-im7xh]

Understood 🔥🔥🔥 Thanks for Your teachings

[@suryashjha7892]

Amazing explanation 🔥🔥🔥

[@AnitaSharma-bk4fc]

Understood thanks striver❤

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@amitpawar8035]

Awesome explanation as always

[@ritikasingh7252]

Awesome explanation👏

[@desihiphop4998]

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

[@addityasharma6426]

understood, great explanation bhaiya😊😊😊

[@komalkrishna7836]

Understood... Thank you!

[@rahulreddy3588]

Understood very well!👌

[@user-ym1nv1pw8i]

Understood! Mark for revision!

[@nirban7689]

//You are a really good teacher. Respect++;

[@thenriquevicentini]

Understood, thanks!

[@052_a_sourabhpathak5]

Damn , this is what tier 3 college should teach in DSA's classess!

[@deepakabari17]

Very well understood 👏👏

[@sunildhiman90]

Hi Striver @takeUforward, one question here, As you said previously if we need to find all possible ways then we try recursion and backtracking, Here again we are saying same thing. So does it mean dp is just the optimized way of solving backtracking problems with time and space both optimized?

[@DPCODE72]

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

[@chahakjain6787]

very easy explanation sir!!

[@aditianand6966]

thank you for making such a good content

[@ratnak5370]

FULLY UNDERSTOOD

[@priyatamkumar518]

understood , a lot of wishes for you

[@raghavmanish24]

uunderstood.....thanku striver

[@NazeerBashaShaik]

Thank you!

[@roydebraj2188]

did it myself feels soo godd hehe

[@creativeprojects217]

thank you sir❣

[@dheerajshukla7008]

understood bhaiya

[@rtadwq...------...----.]

Nicely explained sir

[@vedantsharma2921]

how much time should i give to complete this playlist considering I have placements in 1 month?

[@amalasebastian9968]

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

[@natashadale6333]

Good job 💙🌼

[@riderpd09]

OP explanation BHaiya!!

[@Aladin40chor]

Understood 👑

[@akshitmangotra5370]

understood! Thanks!!

[@GhostVaibhav]

Understood🔥

[@mohitagarwal1888]

This is your only video till now that i didnt understood .

[@shyren_more]

understood, thanks!

[@sparshsharma3150]

Understood bhaiya! 🔥

[@drishtirai864]

Understood ..!!

[@arihantjammar8888]

Understood 😊

[@deepanshudhakate9622]

UNDERSTOOD 🔥🔥

[@jayantmishra6897]

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

[@Shivi32590]

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

[@user-ip7ov5ne8l]

Understood ❤

[@user-ug4sl4gf2x]

Understood 💯

[@genzScarlet]

UNDERSTOOD :)

[@siddheshborse3536]

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

[@amanbhadani8840]

Can anyone tell me ,can we think of solving this problem just like combination sum 1 problem by taking array having element as 1 and 2.I know it would not be optimal but i am just having a thought??

[@adebisisheriff159]

Understood!

[@souravsarkar6107]

Understood thank you sir

[@rupampal07]

Awesome video "UNDERSTOOD"