We have another interesting question over here, which is called climbing stairs.
So the question reads you are climbing a staircase.
It takes N steps to reach the top.
Each time you can either climb 1 or 2 steps.
In how many distinct ways can you climb to the top?
So this is the question and we are given an example.
So if n is equal to two.
So you have two steps over here.
And if this is the case there are two ways of reaching the top.
So you could take one step and again one step.
So that's way one.
And you could take two steps together and reach the top.
So that's way two.
So there are two ways of reaching the top if there are just two steps.
So this is the question at hand.
Now let's just discuss this a bit.
So it says each time you can either climb 1 or 2 steps.
And we need to find the distinct number of ways in which you can climb to the top.
So let's say you have a few steps over here and you're starting over here.
Now in the question it's mentioned that you can either take one step or you can take two steps at a
time.
Now how do we identify that this is a dynamic programming question.
So let's think about that.
So to identify that notice that over here you have choices in place.
You can either take one step or you can take two steps.
So this is a clue that you could probably use dynamic programming.
Because when you have choices at hand we can use recursion.
Also do notice that you will have overlapping subproblems because these are actually two branches right.
So these are two branches.
So this branch is when you start with taking one step.
And this branch over here starts by taking two steps.
Now let's say in both these processes you will reach this step over here.
And then from this step, let's say there are k ways to reach to the top.
So over here notice that reaching this step will happen in both these branches.
And then you would have to calculate k twice if you're not using dynamic programming.
So you have overlapping subproblems.
So again in this branch when you're taking two steps you directly reaching over here.
And when you're taking one steps there is a possibility that the next step is also going to be one step.
And you will reach over here.
So the subproblem of finding the number of ways in which you can reach to the top from this step over
here will happen in both the branches.
So there are overlapping subproblems.
So this is a strong indication that we can use dynamic programming to solve this question.
In fact, we will see how this question over here is an application of the Fibonacci question that we
have previously discussed.
So we have understood the question and we have also identified that this is a dynamic programming question.
Now let's take a look at a few interesting test cases.
As part of the question, we were given an example that if n is equal to two, the output required is
two itself, or there are two distinct ways of reaching the top.
And again these are the two ways you could take one step and one step.
Or you can directly take two steps to reach to the top.
Now if n is equal to three, the output again has to be three.
Because notice if you have three steps.
This is one way which is taking one step at a time.
Then you could take one step initially and then take two steps over here.
So this is one more way.
And you could take two steps initially and then take one more step.
And again the first one that we discussed was taking one steps at every point.
So these are the three ways of reaching the top.
If there are just three steps now if there is just one step, then there is just one way of reaching
the top by taking one step.
So again, these are a few interesting test cases.
Now in the next video let's discuss how you can easily solve this question.