Hi, everyone.
So in this video, we are going to discuss about this question, climbing stairs.
So in this question, what we have given to us is we are standing at the ground floor and we want to
reach to the top.
So these are insteps steps, these are steps and I want to rise to the top, so it is given willing
to take any steps to reach to the top.
And the condition is we can either climb one step or two step.
So either I will take a jump of one or I will take a jump of two from each step and we need to return.
How many distinct ways are there to climb to the top?
So this is the question and it's a pretty simple question we can easily solved with the help of recursion.
So see.
Let me draw this diagram so I want to reach this step, and this is and minus one step.
This is and my is step and and my next steps.
So either I can take a jump of two or one.
So basically I can reach this step and from and minus one by taking a step of one.
Or I can reach this and step by taking a step of two from and minus two.
Right.
So the number of ways, the number of ways to reach and step is basically either you can come from and
minus one step or you can come from and minus two.
So that will be our course relation.
I'm explaining again, I want to reach here so either I can come from and minus one by taking a step
of one or I can count from and minus two by taking a step of two.
So a number of ways to reach and will be the number of ways to reach and minus one, plus the number
of these number of distinct ways to reach and minus two.
So that will be our recursive relation and what will be our best case.
So best case is.
This is ground this is step one and this is ground level.
So how many number of ways to reach at this step?
Only one, right?
I can take a jump of only one.
So we know what is half of one.
Half of one is one.
Right, so we know the reconciliation, we know the base case, let's start writing the code.
So the cold is going to be pretty simple.
We are going to use recursion for solving this problem, so we will return integer number of distinct
ways to climb to the top.
Let's say the name of the function is count steps.
So first, let's talk about the base case, so base cases, if the value of an is one, then how many
steps?
I need to take one step.
Right, so they are done when similarly, if the value of any zero you are standing at the ground level,
then how many steps to take?
None.
Right.
So there is one way we need to return.
How many distinct ways?
So there is one.
We do not do anything.
So there is one way, right.
Now, our caste relation was our answer was.
No steps to reach and minus one plus number of steps to reach and minus two.
And now we just need to call this function.
So they don't count steps and and and that said, this is going to be the complete college right now
and then I will submit.
So summit.
So since this is recursive cold, we are going to encounter a time limit exceeded,
right, because this is recursive cold and we can easily convert this recursive code into a deep code,
which we are going to do in our next video.
And if you click here, we can see how many test cases our code is passing.
So out of 45, if we have passed 21 test cases, our code is failing for the remaining test cases because
of time limit.
So we NextRadio, what they are going to do is we are going to convert the second resolution into DEPI
solution.
Right.
So we will do that in our next video.
So this is a tremendous device.
I will see you in the next one.
Thank you.