Program to count the total number of ways to reach the Nth stair is discussed here.
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)
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 */
int fib(int n)
int countWays(int s)
int main ()
Test Case 1
Test Case 2
Test Case 3
Test Case 4
Test Case 5