Stair Climbing

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.

X | Sequence
------------
2 | 1 1 2 3 5 8
3 | 1 1 2 4 7 13
4 | 1 1 2 4 8 15

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:

def fib(N,X):
  if(N == 0 or N == 1):
    return 1
  if(N < X):
    return fib(N,N)
  if(N >= X):
    ret = 0
    for i in range(1,X+1):
      ret += fib(N-i, X)
    return ret

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