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 N1 steps are left to be taken.
If
we take 2 steps, then N2 steps are left to be taken.
So,
at any stage, no of possible ways to take N steps is:
F(N)
= F(N1) + F(N2)
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.
