Count the total number of ways to reach the Nth stair | faceprep

Program to count the total number of ways to reach the Nth stair is discussed here. 

DESCRIPTION:

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 total number of ways, the person can reach the top.

Sample Input: 4 (Number of stairs)

Sample Output: 5 (Number of ways)

Explanation:

Way 1: 1-1-1-1-1
Way 2: 1-2-1
Way 3: 2-1-1
Way 4: 1-1-2
Way 5: 2-2

Algorithm to count the total number of ways to reach the Nth stair

  • Input the total number of stairs.
  • This problem is clearly recursive.
  • The person can reach the Nth stair from the (N-1)th stair or (N-2)th stair.
  • Recursively call, ways(n) = ways(n-1) + ways(n – 2)

Program to count the total number of ways to reach the Nth stair is given below.

/* C++ program to count the total number of ways to reach the Nth stair */

#include<stdio.h>
int fib(int n)
{
  if(n<=1)
     return n;
  return fib(n-1)+fib(n-2);
}  
int countWays(int s)
{
   return fib(s+1);
}
int main ()
{
 int steps;
 scanf(“%d”,&steps);
 printf(“%d”, countWays(steps));
 return 0;
}

Test Case 1

I/P
4
O/P
5

Test Case 2

I/P
7
O/P
21

Test Case 3

I/P
24
O/P
75025

Test Case 4

I/P
2
O/P
2

Test Case 5

I/P
3
O/P
3