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.
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.
The first test case of input is the T number of the test case, each test case consists of a single integer the nth stair.
Print the number of ways to reach nth stair from bottom in a new line for each test case.
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 Complexity for the above approach in the worst case is exponential.
Space Complexity for the above approach is the liner.
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 the dp 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 Complexity for the above approach in the worst case is : O(n)
Space Complexity for the above approach in the worst case is: O(n)
C++ Implementation (Recursive Approach):
C++ Implementation (Dynamic Programming Approach):
(a) Top Down Approach:
(b) Bottom Up Approach