Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Count ways to reach the n stair

Sharing is caring!

Problem statement
There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top.

Solution
We can solve this problem recursively. If the person were to take 1 step, then we need to solve the problem for n-1 stairs. That is, finding the number of ways to traverse the remaining n-1 stairs. If the person were to take 2 steps then the problem gets reduced to finding the number of ways to traverse the remaining n-2 stairs. Assuming we have a function count(n) that returns the number of ways to traverse n stairs, we would have:

Finally, we need to define our termination conditions:
If there only 3 stairs left, we know that a person can traverse them in three different ways (1+1+1 or 1+2 or 2+1). If there only 2 stairs left, we know that a person can traverse them in two different ways (1+1 or 2). If there is only 1 stair left, we know that a person can traverse them in one way only. These are our recursion-termination conditions.

  • count(3) = 3
  • count(2) = 2
  • count(1) = 1

Above we can see that count(n) is actually equal to fibonacci(n+1):

  • count(3) = fibonacci(4) = 3
  • count(2) = fibonacci(3) = 2
  • count(1) = fibonacci(2) = 1

(Remember: f_0 = 0, f_1= 1, f_2 = 1, f_3 = 2, f_4 = 3, \dots).

We can solve this problem using the fibonacci series. Let us go ahead and define our fibonacci(n) function:

Putting it all together we have: