Find total ways to reach the n’th stair from the bottom

Given a stair case, find total number of ways to reach the n’th stair from bottom of the stair when a person is only allowed to climb either 1 or 2 or 3 stairs at a time.


 

For example,


Total ways to reach the 3’rd stair are 4

1 step  + 1 step  + 1 step
1 step  + 2 steps
2 steps + 1 step
3 steps

 
Total ways to reach the 4’th stair are 7

1 step  + 1 step  + 1 step  + 1 steps
1 step  + 1 step  + 2 steps
1 step  + 2 steps + 1 step
1 step  + 3 steps
2 steps + 1 step  + 1 step
2 steps + 2 steps
3 steps + 1 step

 
Let T(n) be the the total number of ways to reach the n'th stair from the bottom. Since a person is only allowed to climb either 1 or 2 or 3 stairs at a time, we can reach the n'th stair from either (n-1)'th stair, (n-2)'th stair, or from (n-3)'th stair. Considering this, the recurrence relation T(n) can be written as:

T(n) = T(n-1) + T(n-2) + T(n-3) where n >= 0 and
T(0) = 1, T(1) = 1, and T(2) = 2

 
Here’s a C program that implements the above recurrence:

 

Download   Run Code

Output:

Total ways to reach the 4’th stair are 7

 
The time complexity of above solution is exponential since it computes solutions to the same sub-problems again and again i.e. the problem exhibits overlapping subproblems.

The problem has an optimal substructure since a solution to a problem can be derived using solution to its sub-problems. Since both properties of dynamic programming are satisfied, we can use dynamic programming to optimize the code to linear time. This can be done in two-ways:

 

1. Top-Down Approach

We can use memoization to solve this problem in top-down fashion. The idea is to store the results of function calls and return the cached result when the same inputs occur again.

 

Download   Run Code

Output:

Total ways to reach the 4’th stair are 7

 

2. Bottom-Up Approach

We can also use tabulation to solve this problem in bottom-up fashion. The idea is to construct a temporary array which stores the results of each sub-problem using already computed results of the smaller sub-problems. The algorithm can be implemented as follows in C:

 

Download   Run Code

Output:

Total ways to reach the 4’th stair are 7

 
The space complexity of above solution is O(n). The program can be made to run in constant space by storing solutions to only last three sub-problems at any point and discarding the rest. This is demonstrated below in C:

 

Download   Run Code

Output:

Total ways to reach the 4’th stair are 7

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of