Number of ways to climb a staircase using 1 or 2 steps
the person takes n steps of ‘2’ and m steps of ‘1’
then to climb ‘N’ steps, the following equation can be
+ m = N
solutions to the above equation give us a possible way to climb the
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
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.
we take 1 steps, then N-1 steps are left to be taken.
we take 2 steps, then N-2 steps are left to be taken.
at any stage, no of possible ways to take N steps is:
= F(N-1) + F(N-2)
is a fibonacci series, we only need to put some initial values.
F(0) = 0 and F(1) = 1
the above, F(2) = 1+0 = 1
we can see that F(2) can be done in 2 ways as: 1+1 and 2
out that we need to hardcode F(2) also to make this fiboncaai series
F(2) = 2
F(3) = 1+2 = 3 which is correct (1+1+1, 1+2 and 2+1)
= 2+3 = 5 (1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2)
= 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,
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.
we can take 1,2 or 3 steps at each stage.
recursive solution sets in as follows:
= F(1) + 1 (This one is for the independent step of 2)
= F(1) + F(2) + 1 (This one is for the independent step of 3)
= F(1) + F(2) + F(3) (This is where pure recursion sets in)
interesting case is when steps are says 1, 5, 8 (basically when steps
are not just increasing by 1)
we have to consider the initial configurations at various different
F(9) = F(8) + F(4) + F(1)
F(8) = F(7) + F(3) + 1 (This one is the effect of independent step of
F(5) = F(4) + 1
more closely, the above becomes equivalent to the coins problem
one more observation is that if we define F(0) = 1 then we do not
need to consider the cases separately.
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