Welcome back.
Let's start with the intuition required for solving this question.
Now for this, let's take the case where there are three steps.
So if n is equal to three we have three steps.
Now we know that the answer which is expected in this case is three itself because that's a test case
that we had previously written.
Now over here let's make an interesting observation.
Let's say that the number of ways that you can reach the top from this step over here is something that
we know.
And let's say we also know the number of ways in which we can reach the top from this step over here.
Now, if we know that, then the number of ways of reaching the top or the answer to this problem would
be the sum of those two values.
Now why is that the case?
Let's think about it for this.
Let me number the steps over here as one, two and three.
And let's say that this over here is equal to b.
So there are b ways of reaching the top from step one.
And there are a ways of reaching the top from step number two.
Now notice that for each of the b ways which we have identified over here, we can reach the top without
going to step number two in just one way, which is directly going from step one to step three.
Similarly, for each of the A ways in which we were able to reach step number two, we are able to reach
the top by just taking one step.
So this means that when we identify that we can reach this step in b ways, we have actually identified
the number of ways in which we reach over here and reach the top without going to step number two.
So that's what actually B is.
Similarly a ways, which is the number of ways of reaching this step, is actually the number of ways
of reaching this step and reaching the top.
So that's why we can say that the number of ways of reaching the top is just B plus a.
Now let's generalize this.
Let's say that instead of three this is n.
Then this would be n minus one.
And this would be n minus two.
Let's make some space over here.
So what we have seen is the number of ways of reaching step number three is equal to the number of ways
of reaching step number one, plus the number of ways of reaching step number two.
Or in other words, the number of ways of reaching step number n is equal to the number of ways of reaching
step number n minus one, plus the number of ways of reaching step number n minus two.
So notice that what we have over here is the same thing that we had for the Fibonacci question, where
it was given that f of n is equal to f of n minus one plus f of n minus two.
So that's why this question is actually the same Fibonacci question put forth in a different way.
Or it's an application of the Fibonacci question.
So you can solve this question using the same approach that we have discussed for the Fibonacci question.
And I would highly recommend that you first write the recursive solution.
Then you can memorize it.
And after that write the tabulation approach as well as the space optimized tabulation approach.
So this is an awesome question to practice on your own and to solidify your learning and remember the
time and space complexity of these solutions that you're going to write will be the same as what we
have discussed for these respective approaches when we discussed the Fibonacci question.