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

[@utkarshyadav3401]

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

[@ArathiK-s8u]

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.

[@parthdurgude2617]

yeahh I too love to listen to it...

[@adityagaur4686]

How do u get the job bruh

[@Abhinav-b2k]

@@adityagaur4686 Not everyone is a doofus like you, doing dsa only wont get u anywhere

[@anbazhagane1266]

MAN I waslooking for this help to figure out wat song Is this?

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

[@Tron.f]

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

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

[@stith_pragya]

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

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

[@manantyagi6905]

Bestest stuff of all the cases of tutorials on youtube

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

[@syedakhudsiyatarannum5695]

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

[@Madhugunupudi]

Actually, I don't know how to thank you! Seriously, you're incredible-that's all!

[@sukhpreetsingh5200]

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

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

[@yt_ac]

Day - 1 : understood the three points clearly

[@lifehustlers164]

3/57 done!!! Understood!

[@vishalchoudhary5918]

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

[@RAHULKUMAR-sx8ui]

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

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

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

[@dharmeshpoladiya9047]

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

[@rajneeshmishra6969]

Understood! Loved how you simplified the recurrence relations thing!

[@lakshmichandhana]

Amazing Lectures ,learnt a lot .Great initiative.

[@yashshukla1637]

Done. Learned about the 3 step DP process.

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

[@likhitbhogadi]

thanks bro, understood..

[@rashmikareddy3259]

Learning to be consistent from you sir.. UNDERSTOOD

[@ganapathyg981]

Thanks for explaining in English.. love from Tamilnadu 😎

[@atech_guide]

Great Explaination in building the recursion. Thanks

[@poisegaming2448]

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

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

[@Sanya-ic8gr]

UNDERSTOOD! Thank you striver!!

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

[@ekta9145]

Understood! Thank you very much, sir.

[@sakshiupadhyay3284]

More power to you striver... "UNDERSTOOD"

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

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

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

[@AnitaSharma-bk4fc]

Understood thanks striver❤

[@punitgarg4627]

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

[@035asadali8]

he mentioned in video ,u missed

[@shivammishra2413]

understod.thanks striver bhaiya ❤

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

[@Likithreddy...2310]

understood thanks for the resource

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

[@Lakshya-f4l]

Understood! Mark for revision!

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

[@easycode3189]

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

[@DeveshKumar-tj2rs]

UnderStood To create any recurrence relationship 1. Treat the the question in the forM of indexing 2. Do all possible things on the index 3. Count or fine min of max to get your and.

[@creativeprojects217]

thank you sir❣

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@jayantsingh2863]

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?

[@amalasebastian9968]

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

[@programmertik2046]

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

[@SwapnilChavan-im7xh]

Understood 🔥🔥🔥 Thanks for Your teachings

[@shivanshumishra0560]

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

[@maheshgundlapalli4690]

thank you striver

[@anonymous-hf9ju]

understood 🙏

[@AshutoshShuklaaa]

def Climbing_Stairs(n): if n

[@aagamjain2131]

Awesome explanation!! Understood sir 🔥💯

[@ashishabhinandanvlogs6083]

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

[@avakanksh]

UNDERSTOOD. But there is a small issue in the base case, n = 0 doesn't make any sense according to the problem, so we need to set the base case as n = 1 and n=2. Rest everything is understood. Thanks for the videos

[@codecrafts5263]

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

[@Aladin40chor]

Understood ❤👑

[@BhavyaJain-qz8jg]

understood👍👍

[@somnathroy102]

This is so simple. Thank you Understood.

[@lakshaysharma6550]

"UNDERSTOOD!!!!!!!!!!!!!!!!!"🔥🔥🔥🔥🔥🔥🔥🔥

[@aps8874]

Thank you 💓

[@studytable2060]

for index=1 why return 0 can you explain as it should be return 1 because there is only 1 way to reach index 1 from 0

[@aps8874]

​@@studytable2060 Look at 10:05 timestamp, he has provided correction for the same.

[@perveenneha1423]

understood heart felt thank you

[@nantuadhikari1280]

Understood 💥💥💥💥

[@insofcury]

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

[@gokulanvs]

Understood❤❤❤

[@raghavmanish24]

uunderstood.....thanku striver

[@senseiAree]

Understood❤ 😊

[@siddheshborse3536]

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

[@rahulreddy3588]

Understood very well!👌

[@suryashjha7892]

Amazing explanation 🔥🔥🔥

[@thenriquevicentini]

Understood, thanks!

[@nithishlelll9664]

understood!😇

[@ShivamDangwal-n1o]

Understood 💯

[@shaikkhizar8133]

Understood striver

[@aryankumar87771]

Python Most optimized solution => def climbStairs(self, n: int) -> int: prev = 1 prev2 = 1 res = 1 for x in range(2,n+1): res = prev + prev2 prev2 = prev prev = res return res

[@shivaprasadkoyyada9723]

yeah but the concept is on dp ...

[@NazeerBashaShaik]

Thank you!

[@052_a_sourabhpathak5]

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

[@deepanshudhakate9622]

UNDERSTOOD 🔥🔥

[@banothutharun2743]

Understood brother

[@desihiphop4998]

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

[@yashrawat5158]

//memoization #include #include using namespace std; int frog(int n,vector &dp){ //base case explanation // If n is 0, the function returns 1. This is because if the frog is already at position 0, then it doesn't need to make any more jumps to reach position 0, so there is only 1 way to do so. //If n is 1, the function returns 1 as well. This is because if the frog is at position 1, it can only make one jump of 1 step to reach position 0, so there is only 1 way to do so. if(n==0){ return 1; } if(n==1){ return 1; } // condition for dp if(dp[n]==-1){ int left=frog(n-1,dp); int right=frog(n-2,dp); return dp[n]=left + right; } else{ return dp[n]; } } int main(){ int n; cin>>n; vector dp(n+1,-1); cout

[@TheAI-Tutor]

bhai, if the frog is already at position 0, then it doesn't need to make any more jumps to reach position 0, SO IF oesn't need to make any more jumps to reach position 0, THEN WHY DOES HE NEED TO JUMP IF HE HAS ALREADY ARRIVED THERE? I'M V CONFUSED ABOUT THIS

[@Aladin40chor]

Understood 👑

[@UECAshutoshKumar]

Thank you sir Understood

[@ashokm6528]

Understood three points ❤

[@roydebraj2188]

did it myself feels soo godd hehe

[@arihantjammar8888]

Understood 😊

[@gouravdutta9464]

Understood

[@sparshsharma3150]

Understood bhaiya! 🔥

[@addityasharma6426]

understood, great explanation bhaiya😊😊😊

[@TarunKumarSaraswat]

watching for 2nd time , makes more sense now

[@priyatamkumar518]

understood , a lot of wishes for you

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

[@chahakjain6787]

very easy explanation sir!!

[@natashadale6333]

Good job 💙🌼