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.

- 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.
- Initialize DP[0] = 1, DP[1] = 1, DP[2] = 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.
- 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[0]=1; dp[1]=1; dp[2]=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.*

## 2 comments