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

Leave a Reply

Your email address will not be published.