# Stair Climbing

#### Posted on March 26, 2013

##### Last updated on July 30, 2013

Problem Statement:

You are at the bottom of a staircase of $$N$$ steps. Each time, you can either go up by one step, or go up by two steps (skipping a step inbetween). How many ways are there of climbing the staircase ?

Let us call the number of ways to climb a staircase of $$X$$ stairs $$f(X)$$. The answer we are looking for then is $$f(N)$$. As you might have noticed, this problem will involve recursion. Let’s look at the base cases. There is only one way of climbing a staircase of $$0$$ steps, that is to take no steps at all. For a staircase of one way, you have precisely one way of climbing it - you take one step. Hence, the base cases are: $F(0) = 1 \\ F(1) = 1$ Imagine now you are the top of the staircase of $$N$$ steps. You had two ways of getting there. Either, you were on step $$N-2$$ and took a step of size $$2$$, or you were at step $$N-1$$ and took a step of size $$1$$. Hence, the number of ways to getting to step $$N$$ is recursively defined in terms of $$N-1$$ and $$N-2$$. $F(N) = F(N-1) + F(N-2)$ You might notice that the solution to this problem is the Fibonacci sequence!

Now that we have the answer for the case of taking a step of size one or two each time, we can generalize the problem by saying that at each time you take a step, you can step anywhere between $$1$$ and $$x$$. Let us define the number of ways to climb a staircase of $$N$$ steps, each time taking a step of size from $$1$$ to $$x$$, as $$F_x(N)$$. The solution to the above problem is then $$F_2(N)$$.

Firstly, let’s write out some of the solutions by hand to get the intuition behind the problem.

Let’s look at the case of $$X=3$$. For $$N=0$$, $$1$$, $$2$$, the solutions are exactly the same as for $$X=2$$. This is because a step of size $$3$$ is useless to us when we need to cover a distance of length less than $$3$$. Then, for any $$N$$, $$N<X$$, the solution is simply $$f_N(N)$$.

Otherwise, if $$N \geq X$$, we can calculate $$f_X(N)$$ just like in the simple $$X=2$$ case, $$f_X(N) = \sum_{i=1}^{X}f_X(N-i)$$.

We now have the full recursive formulation, which we can translate to Python as follows:

This is just a generalization of Fibonacci numbers. You can of course memoize the above piece of code.