# Number of ways to reach N’th stair (DP-17)

Count the number of ways to reach N’th stair starting from 0th staircase if you can take a jump of 1, 2 or 3 stairs at a time.

Sample Input: N = 4
Expected Output: 7
Explanation: Following are the ways through which you can reach 4th stair – {{1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {1, 2, 1}, {2, 1, 1}, {2, 2}, {3, 1}}

Algorithm:

The problem can be solved using Dynamic Programming as it has both optimal substructure and overlapping sub-problem.

1. Create an array DP of size (n+1) to store the results of the sub-problems. DP [i] denotes the number of ways to reach i’th stair from 0th stair.
2. Initialize DP = 1, DP = 1, DP = 2. Because to reach 0th stair from 0th stair, we have 1 way that is to not do anything. To reach 1st stair from 0th stair, we can take a jump of 1 stair. To reach 2nd stair, we have two ways.
3. For all other values of i (2<=i<=N), we do the following. Set DP [i] = DP[i-1] + DP [i-2] + DP [i-2]. Here, DP [i-1] denotes the number of ways to reach i’th stair by jumping 1 staircase, DP [i-2] denotes the number of ways by jumping 2 stairs and DP [i-3] denotes the number of ways by jumping 3 stairs.
```#include <bits/stdc++.h>
using namespace std;

int helper(int n){
vector<int> dp(n+1, 0);
dp=1;
dp=1;
dp=2;
for(int i=3; i<=n; i++){
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}
return dp[n];
}

int main(){

int n=4;
cout<<helper(n);

return 0;
}```

Also, check out another popular interview question Activity selection problem.