Home Practice Programming Count number of ways to reach the nth stair by climbing 1,...

Count number of ways to reach the nth stair by climbing 1, 2 or 3 steps

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3
steps at a time. Implement a method to Count number of ways to reach the nth stair by climbing 1, 2 or 3 steps at a time.

Example:
    stairs n = 3   steps = 4
    stairs n = 4   steps = 7
    stairs n = 5   steps = 13
Algorithm

Suppose given n stairs, and currently, and we are at the ground(stair 0), then at a time we can go to either :
a. stair 1, remaining stairs = n-1
b. stair 2, remaining stairs = n-2
c. stair 3, remaining stairs = n-3

Let’s say we have 3 stairs:

Number of ways to climb 3 stairs
Number of ways to climb 3 stairs

In the above diagram, values(steps) marked yellow are being recomputed. To avoid this recomputation, we will use Dynamic Programming (i.e, by saving the result when we calculate the first time and using the saved result next time).

Implementation of the above algorithm in CPP
#include <bits/stdc++.h>
using namespace std;

int total_steps(int n, vector<int>&dp){
	
	if(n<0)
		return 0;
	
	if(n==0||n==1)
		return 1;
	
	if(dp[n]==-1)
		dp[n] = total_steps(n-1,dp) +total_steps(n-2,dp) +total_steps(n-3,dp);	
	
  return dp[n];
}

int main()
{
	int n;
	cin>>n;
	vector<int>dp(n+1,-1);

	cout<<total_steps(n,dp)<<endl;

	return 0;
}
Output
   n = 3,   output: 4 
   n = 4,   output: 7 
   n = 28,  output: 15902591
Time Complexity

Time Complexity of the above program using Dynamic Programming is O(N), where N is the number of stairs.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promsie, we won't spam
Even we hate spam as much as you hate them

Books recommendation for interview preparation