hey everyone welcome back to the channel i hope you guys are doing extremely well so welcome back to the second lecture of the dynamic programming playlist we're going to solve a problem which is count ways to reach the nth stairs yes so what does the problem actually state it states that you'll be given a number of stairs so you'll be given n which is the number of stairs initially you are at the zeroth state that means you are at the zeroth state okay and you need to reach the nth stair like you have to reach the nth stair now each time you can either climb one step or you can either climb couple of steps now you're supposed to return the number of distinct ways in which you can climb from the zeroth step to the nth step now for an example if i'm giving you n uh is equal to three then i can say if from the zeroth step i take one step then i take one more step then if i take one more step i'm going to reach the third or from zero if i take two step and then i take one step i'm going to reach the third or from zero if i take one step then if i take two steps i'm going to reach the third so i can see these three are three distinct ways in which you can reach the third step so the problem is very simple uh you have to tell me the distinct ways in which you can reach the third step so the problem is very simple and straightforward you have to tell me the distinct ways in which you can reach the nth stair if you start from the zeroth stair so remember one thing uh in all the 1d uh problems like generally in dp in all the 1d problems i'll be telling you away so first let's understand how do you uh how do you understand that this is a dp problem like that's the first step before applying dp you have to understand that this is indeed a dp problem now whenever they say whenever the questions are like this generically whenever the questions are like this count to be the total number of ways so that's the first point count the total number of ways the next can be uh probably there might be multiple ways of doing something and they're asking you to figure out which gives you the minimum output or the max output so the question might be like there are multiple ways to do this but you gotta tell me uh which is giving you the minimal output or maximum output generally in these kind of questions you tend to apply recursion why because if i'm saying you count distinct ways that means i'm saying you that okay figure out how many ways are there so you have to try all possible ways remember this whenever the concept of try all possible way comes in try all possible ways comes in whenever it can be any way if the concept of try all possible ways comes in and if there is like count or if there is like figure out the best way if out of all the possible ways you have to figure out count like how many ways are there or the best way that's when you try to apply recursion what did i say that's when you try to apply something as recursion where you try all possible ways and if you remember in the lecture 7 of the recursion playlist in the lecture 7 of the recursion playlist i told you if you have to count all ways then you have to perform all the ways and then sum it up if you have to figure out the best way then you have to perform all the ways and tell which is the best among them so you'll understand these things in depth but as of now just understand that whenever the problems tells you to figure out or like try out all possible ways then you tend to think of recursion when recursion says i'm going to try all possible ways whether i can count or probably i can found the best that's when you think of recursion and once you think of recursion then you can think of dynamic programming but the first step is try to figure this out that this is a recursive problem that's the first step behind every problem like over here like over here it was n equal to three so you're like okay from zero you will take one step to one from one you'll take one step to one from two you'll take one step to one and you'll reach three or from zero you'll take two steps to two then you'll take one step to uh three you'll reach or from zero you'll take one step to one then you'll take two steps to three so these were the three possible ways in which you can reach so what is this giving you an idea try all possible ways yes so a lot of people say that if you can master recursion you can master dp so i'm gonna teach you a trick i'm gonna teach you a shortcut trick which will be helpful in all the problems in db and you will be able to write every recurrence relation so the step one of that trick is try to represent the problem in terms of index like if it's an array problem there will always be an index but if it's not an array problem then also try to represent the problem in terms of index remember this you will always do this try to represent the problem in terms of index next do all possible stuffs on that index do all possible stuffs on that index according to the problem statement according to the problem statement step 3 if the question says count all the ways sum up all stuffs sum up all stuffs if the question says count always if the question says find minimum take minimum of all stuffs okay if the question say it's fine minimum similarly the question says find maximum you'll take the maximum remember this three points if you remember these three points you can solve any recurrence and if you are able to write the recursion then you can memoize it to convert it into dp and then you can tabalize it and after that you can space optimize it okay so over here what was the problem the problem was you are at zero and you have to reach n the person has to reach n so assume assume uh this is not an array this is like 0 to n the stairs assume these stairs to be indexes i call a 0 to be an index i call 1 to be an index 2 to be an index 3 to be an index 4 to be an index 5 to be an index and everything assume i'm calling them as index treat them as an index okay so step one i've understood how will i represent this problem in terms of index that is something which i've understood now next step is to realize what will your recursion give so i can say if i write a recursion that recursion should tell me the number of ways in which i can reach from 0 to n if i'm calling a recursion as f n he should tell me what are the number of ways in which i can reach from 0 to n that should be the recursions job i am like yeah that's true so what if i uh write it as f of index so can i say the base case is very simple if if i'm standing at the zeroth stair there is no other way like there's only one way in which i can like if i'm standing at zero there's only one way right i cannot jump there's only one way next we have converted the problem in term of in terms of uh index what's the step number two do all possible stuffs on that index yes do all possible stuffs on that index what are the question stating either it can jump one either it can jump to so from a stair you can jump one or you can jump two so what can you do on that index jump one or jump two do it nah what are you waiting for so i can say one of the things that i can do is jump one so if you're starting like if you're going from top to down if you jump one you will go back one index if you jump to you will go to index simple correct now now what now can i see okay that's that's pretty pretty perfect now can i say one thing if i can jump one index and if i can jump two index there are a couple of ways in which i can jump so there are a couple of steps that i can do now if someone is saying me to count all distinct ways i know recursion will do its job because you'll go in depth and count all the ways lecture seven please go and watch our lecture seven i've talked to you about how does it count all the ways if you return one at the base case please go and watch our lecture seven if you haven't because over there i've taught you how do you count always by returning a one on the base case i've taught you that so please watch out lecture seven in the recursion pause it if you haven't watched it so you know how to count always if this is the left recursion and this is the right recursion in order to count all the ways i told you right you have to return left plus right that's what you need to do so if you write this recursion it is going to work but still there's an edge case yeah there is an edge case so can i say can i say that if you're doing index minus 2 now think about these edge cases i did not tell you what if you are standing at 1 what if i'm just calling f of 1 then 1 minus 2 will become minus 1 so there might be a problem so you can introduce one more h case something like this again if index is equal to equal to one so can i say uh if you're standing at one there's only one way in which you can go zero so you can return a zero done what is this uh looking like like what do you think which question is this like i'll be like yeah this is fibonacci yeah absolutely you solve this problem in the previous one so you saw this how i took a different problem how i analyzed it and converted it into fibonacci so what i can say is this problem is nothing but similar to fibonacci number if you carefully write the recurrence and the possible ways to write a recurrences try to represent the problem in terms of index do all possible stuffs on that index if it is saying if the question is saying count always you will sum up all the stuffs if the question is saying find minimum you will take minimum of all the stuffs that is how you should solve any given question now so you can easily memorize it after that you can convert into the tabular form and then after you can space optimize it and we have already done this in the lecture one so i'll not be doing that again the main reason why i picked up this problem was to tell you even if i did not know this was a fibonacci i told you how to write the returns and after that you figured out it's a fibonacci and even if you don't know fibonacci you can definitely solve this problem now in in code studio if i take you to the code studio the value of n is given as 10 to the power 18. so either in the tabular form even if you run a for loop you cannot run a for loop till 10 to the power 18. even if you uh the space optimization you cannot run a for loop till 10 to the power 18. so a big o of n approach will not work so in order to find fibonacci uh you have to actually use matrix exponentiation which helps you to find this in logarithmic of n probably i can discuss this in some other lecture but the main main focus of today's lecture was to tell you how to convert any unknown problem to a recurrence and then then you can easily write the tabular and the space optimized i'm not writing the tabular space optimized in this lecture because i've already done that in done that in the lecture one okay if i would have not done that in the lecture one i would have done it over here but i'm just skipping it because i've already done it so please remember these three points are important which i wanted to convey you in this particular lecture so the main intention of this lecture was to teach you the shortcuts the three points which helps you to build the recurrence because after that it's memoration then tabulation and then space optimization so i hope you have got this keep these three points in your brain because in the next lecture we will be solving a problem which will be much much more interesting and you can use these three points to solve that particular problem as well so with this let's wrap up this video and yes as a trend please please write understood uh if you have understood this particular lecture and the three points and make sure you like this video and if you're new to this channel please please please do consider subscribing to us and yeah with this let's wrap up this video bye take care whenever your heart is [Music]