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:

answer = count(n-1) + count(n-2)

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:

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

Putting it all together we have:

public class NumberOfWays {
    public static int fibonacci(int n) {
       if (n <= 1) {
          return n;
       } else {
          return fibonacci(n-1) + fibonacci(n-2);
       }
    }
     
    public static int count(int s) {
        return fibonacci(s + 1);
    }
 
 
    public static void main (String args[]) {
          int s = 4;
          System.out.println("Number of ways = "+ count(s));
    }
}