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:
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.