Make delicious recipes!

Number of ways to climb a staircase using 1 or 2 steps


If the person takes n steps of ‘2’ and m steps of ‘1’ then to climb ‘N’ steps, the following equation can be written:

2n + m = N


All solutions to the above equation give us a possible way to climb the staircase.

However, solution to the above do not capture the order of climbing and treats all orders of climbing as same if the number of 2 steps and 1 steps are same in them. For example if n=1 and m=2, then the above says that there is only 1 way but if we consider the order too, then there are 3 ways as: 2+1+1, 1+2+1 and 1+1+2


To capture the order we need to consider the possibility of taking 1 or 2 steps at each stage and see which of them leads to the solution.


If we take 1 steps, then N-1 steps are left to be taken.

If we take 2 steps, then N-2 steps are left to be taken.


So, at any stage, no of possible ways to take N steps is:

F(N) = F(N-1) + F(N-2)


This is a fibonacci series, we only need to put some initial values.

Clearly, F(0) = 0 and F(1) = 1

Using the above, F(2) = 1+0 = 1


But we can see that F(2) can be done in 2 ways as: 1+1 and 2

What went wrong?

Turns out that we need to hardcode F(2) also to make this fiboncaai series work.

Let F(2) = 2


Then F(3) = 1+2 = 3 which is correct (1+1+1, 1+2 and 2+1)

F(4) = 2+3 = 5 (1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2)

F(5) = 3+5 = 8 (1+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 2+2+1, 2+1+2, 1+2+2)


So the above is indeed a fibonacci series with one exception - we need to provide initial values for 3 cases rather than 2. This is so because we have 2 independent variables (1 and 2) which do not depend on each other and have the ability to affect the computation independently. If there were 3 independent steps, then we would have needed to provide 3 initial configurations.


Consider we can take 1,2 or 3 steps at each stage.

Then recursive solution sets in as follows:

F(0) = 0;

F(1) = 1;

F(2) = F(1) + 1 (This one is for the independent step of 2)

F(3) = F(1) + F(2) + 1 (This one is for the independent step of 3)

F(4) = F(1) + F(2) + F(3) (This is where pure recursion sets in)


An interesting case is when steps are says 1, 5, 8 (basically when steps are not just increasing by 1)

Then we have to consider the initial configurations at various different stages.


So F(9) = F(8) + F(4) + F(1)

But F(8) = F(7) + F(3) + 1 (This one is the effect of independent step of 8 steps)

Similarly, F(5) = F(4) + 1


Looking more closely, the above becomes equivalent to the coins problem discussed next.


Also, one more observation is that if we define F(0) = 1 then we do not need to consider the cases separately.

However, if N was really zero, then we should not return 1. This can be solved by creating a wrapper function which return 0 if N is 0 the first time itself. Rest all the times, it simply uses normal recursion of fibonacci series.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal