Climb the Stairs

Introduction

The problem covered by this chapter is a classical one, that has been asked during interview at big tech companies like Amazon or Google. It shares the underlying structure and key properties with many other problems and thus, not surprisingly, also its solution is very similar to theirs (for instance there is a one-to-one correnspondence with the coin change problem and the solution described in this chapter can be used to solve that problem too.). The tecniques discussed in the chapter can be applied to all problem which statements goes like this: Given a target find minimum (maximum) cost / path / sum to reach the target. Usually the problem should be tackled by using the following approach: Choose minimum/maximum path among all possible paths before the current state, then add the value for the current state. Words like state and current will be clearer by the end of the chapter.

Problem statement

You are climbing a stair case and it takes $$n$$ steps to reach to the top.

Each time you can either climb $$1$$ or $$2$$ steps. In how many distinct ways can you climb to the top?

Given $$n = 3$$ the answer is $$3$$ because there are three ways (See Figure 8.1 to climb to the top of the stairs:

1. $$1$$ step + $$1$$ step + $$1$$ step

2. $$1$$ step + $$2$$ steps

3. $$2$$ steps + $$1$$ step

Given $$n = 4$$ the answer is $$5$$ because there are five ways (See Figure 8.2 to climb to the top of the stairs:

1. $$1$$ step + $$1$$ step + $$1$$ step + $$1$$ step

2. $$2$$ steps + $$1$$ step + $$1$$ step

3. $$1$$ step + $$1$$ step + $$2$$ steps

4. $$1$$ step + $$2$$ steps + $$1$$ step

5. $$2$$ steps + $$2$$ steps

Clarification Questions

Can the size of the stair be zero?

Yes, the staircase can be made of zero steps.

It is guaranteed the answer to fit a built-in integer?

Yes, do not worry about overflow.

Discussion

This is probably one problem that it is easier to tackle by first looking at a few examples so it is easier to see patterns. Table 8.1 shows how many ways there are to climb a stair of lenght $$n$$ up to $$n=7$$.

All the ways to climb a stair of lenght $$n \leq 7$$
$$n$$ Ways
$$0$$ $$0$$
$$1$$ $$1$$
$$2$$ $$2$$
$$3$$ $$3$$
$$4$$ $$5$$
$$5$$ $$8$$
$$6$$ $$13$$
$$7$$ $$21$$

[tab:stairs_climbing_ways_up_tp_7]

Looking at the table one thing should be immediately noticed i.e. the number of ways to climb the stair of size $$n$$ is equal to the $$n^th$$ element of the Fibonacci sequence (starting with two $$1$$). Once tht is clear then the solution is straightforward as shown in Listing [list:stairs_climbing_fibonacci].

Listing 1: Solution to the stairs climbining problem with steps of size $1$ and $2$ using Fibonacci.

/*int fibonacci(int k)
{
int p = 0, c = 1;
while(k--)
{
const int tmp = c;
c = p+tmp;
p = tmp;
}
return p;
}*/

int fibonacci(int k)
{
if (k <= 1)
return 1;
return fibonacci(k - 1) + fibonacci(k - 2);
}

int stair_climbing_fibonacci(const int n)
{
if (n <= 1)
return n;
return fibonacci(n);
}

Now, let’s have a look at why the seemingly unrelated fibonacci sequence plays a role in this problem. If the problem is looked at as an iterative process in which at each step a certain number of stairs are climbed. For instance if $$n = 3$$ and:

• $$1$$ step is hopped then the number of remaining steps is $$3-1 = 2$$.

• $$2$$ steps are hopped then the number of remaining steps is $$3-2 = 1$$.

When one step is hopped, the problem changes from climbing $$n$$ stairs to $$n-1$$ stairs. At this point the problem is seemingly unchanged except for the number of stairs left to climb and the same reasoning can be applied again:

• $$1$$ step is hopped then the number of remaining steps is $$(n-1)-1 = n-2$$.

• $$2$$ steps are hopped then the number of remaining steps is $$(n-1)-2 = (n-3)$$.

As can be seen, two decisions are possible i.e. climbing one or two stairs, exactly like in the fibinacci sequence, until either the $$n$$ step or a point past to it is reached.

Common Variation

Arbitrary step lengths

But what happens when the step sizes allowed are not just $$1$$ or $$2$$ but an array of $$k$$ positive values $$A=\{s_1 < s_2 < \ldots < s_k\}$$. The problem statement for this harder variant of the problem is as follows:

You are climbing a stair case and it takes $$n$$ steps to reach to the top.

Each time you can either climb $$s_1$$ or $$s_2$$ or $$\ldots$$ or $$s_k$$ steps where $$0 < s_1 < s_2 < \ldots < s_k$$. In how many distinct ways can you climb to the top?

Note how this problem is equivalent to the easier version described in Section 8.1 when the allowed step sizes are $$s_i = 1$$ and $$s_2=2$$.