How To 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:

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.

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:

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:

Output:

Total ways to reach the 4’th stair are 7

Leave a Reply

Your email address will not be published. Required fields are marked *