# Find Total Ways to Reach Nth Stair from Bottom

You are given a staircase, you need to find the total number of ways to reach the nth stair from the bottom of the staircase when you are only allowed to climb 1, 2 or 3 stairs at a time.

**Problem description:**

The problem needs you to find total possible ways through which we can reach our destination, we are allowed to take a stride of a maximum of 3 jumps from the current position. You are required to develop a certain algorithm that can find the total possible arrangement such that you can reach your destination in minimum possible time constraints.

**Input:**

The first test case of input is the *T* number of the test case, each test case consists of a single integer the *n*th stair.

**Output:**

Print the number of ways to reach *n*th stair from bottom in a new line for each test case.

**Examples:**

Input:
T = 1
N = 4
Output:
7, total possible ways:
1+1+1+1
1+1+2
1+2+1
1+3
2+1
2+2
3+1

1) Recursive Approach:In this approach, we will make recursive calls each time until our base case reaches. We have the following base case:

Now each of the current stairs depends on the previous three stairs since we can take 1 2 or 3 step climb from the current step.

Therefore the overall recursion function

f(n)becomes:Time Complexityfor the above approach in the worst case isexponential.Space Complexityfor the above approach is theliner.2) Dynamic Programming Approach:(a): Top Down Approach:In this approach we will use memorization technique, we create a

dp[]state which are initially filled with -1, each time we calculate the state we fill thedp[]state, and each time we make recursive call we first check if the value is already calculated or not, if calculate then directly return it without calculating it again and again.(b) Bottom Up Approach:In this approach we will fill the

dp[]state in bottom up manner in the following manner.Time Complexityfor the above approach in the worst case is :O(n)Space Complexityfor the above approach in the worst case is:O(n)C++ Implementation (Recursive Approach):Output:C++ Implementation (Dynamic Programming Approach):(a) Top Down Approach:

Output:(b) Bottom Up ApproachOutput: