Count ways to reach nth stair

Count ways to reach nth stair

Problem is to count number of ways a person can reach to top of n stairs, given that he can move 1 or 2 stairs at a time. For example,

count number of ways to reach nth stair

n = 1, number of ways 1
n = 2, number of ways 2 (1,1), (2)
n = 4, number of ways 5 (1,1,1,1), (1,1,2), (1,2,1),(2,1,1), (2,2)

This problem is usually asked to check if you have basic understanding about recursion and can you reduce problems to subproblems and solve them recursively. Counting number of ways to reach nth stair is nothing but modified version of fibonacci series.

Count ways to reach nth stair : reduction

Original problem to climb nth stair is reduced to (n-1)th stair once person moves 1 stair or to (n-2)th stair, if person moves 2 stairs. Now, all you have to solve is to count number of ways person can climb (n-1) and (n-2) stairs.

Ways(n) = Ways(n-1) + Ways(n-2)

Now that you have come up with recurrence relation, when do you stop? Termination condition is must for any recursion. Think what happens when person has only 1 stair to climb? In how many ways he can do it? There is only one possible way, to climb that stair. What if there are last two stairs? Then there are two ways to solve, climb one step at a time or climb  two stairs. This gives us base cases

Ways(1) =  1; Ways(2) = 2

Recursive implementation to count ways to reach nth stair

#include <stdio.h>

int findWays(int n)
{
   if(n==1 || n==2) return n; 
   return findWays(n-1) + findWays(n-2);
}

int main ()
{
  int n = 4;
  printf("Number of ways = %d", findWays(n));
  return 0;
}

Complexity of recursive implementation to count ways to reach nth stair is exponential. Look at the recursive tree of implementation and it becomes evident that there are many subproblems which are calculated multiple times.

count number of ways to nth stair

What is the best way to avoid recalculation? Memoization. Replace recursive function with stored value. Going further, we can use dynamic programming. Create a 1 dimensional array and initialize A[1] =1 and A[2] = 2. Now, to calculate A[3], we can use information already stored in A[1] and A[2]. A[4] can be calculated using A[3] and A[2].

Dynamic programming implementation to find number of ways t nth stair

#include<stdio.h>

int countWays(int n ) {
    int table[n+1];
    table[1] = 1; table[2] = 2;
    for (int i=3; i<=n; i++){
       table[i] = table[i-1] + table[i-2];
    }
    return table[n];
}

int main ()
{
    int n = 4;
    printf("Number of ways = %d", countWays(n));
    return 0;
}

Complexity of dynamic programming approach is O(n) and with additional space complexity O(n).

Please share if there is something is missing or wrong. If you want to contribute to algorithms and me, please contact us.