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.
1 step + 1 step + 1 step
1 step + 2 steps
2 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:
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.
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.
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:
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: