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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <stdio.h> // Recursive function to find total ways to reach the n'th stair from bottom // when a person is allowed to climb either 1 or 2 or 3 stairs at a time int totalWays(int n) { // base case if (n < 0) return 0; // base case: there is one way to cover it with no steps if (n == 0) return 1; // combine results of taking 1 step or 2 steps or 3 steps at a time return totalWays(n - 1) + totalWays(n - 2) + totalWays(n - 3); } // main function int main(void) { int n = 4; printf("Total ways to reach the %d'th stair are %d", n, totalWays(n)); return 0; } |

`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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <stdio.h> #include <stdlib.h> // Recursive DP function to find total ways to reach the n'th stair from bottom // when a person is allowed to climb either 1 or 2 or 3 stairs at a time int totalWays(int n, int dp[]) { // base case if (n < 0) return 0; // base case: there is one way to cover it with no steps if (n == 0) return 1; // if the sub-problem is not seen before if (dp[n] == 0) { // combine results of taking 1 step or 2 steps or 3 steps at a time dp[n] = totalWays(n-1, dp) + totalWays(n-2, dp) + totalWays(n-3, dp); } // return the sub-problem solution return dp[n]; } // main function int main(void) { int n = 4; // create an array of n+1 size for storing solution to the sub-problems // and initialize it by 0 int dp[n+1]; memset(dp, 0, sizeof(int) * (n+1)); printf("Total ways to reach the %d'th stair are %d", n, totalWays(n, dp)); return 0; } |

`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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <stdio.h> // DP function to find total ways to reach the n'th stair from bottom // when a person is allowed to climb either 1 or 2 or 3 stairs at a time int totalWays(int n) { // create an array of n+1 size for storing solutions to the sub-problems int lookup[n + 1]; // base case: 1 way (with no steps) lookup[0] = 1; // There is only 1 way to reach the 1st stair lookup[1] = 1; // There are 2 ways to reach the 2nd stair lookup[2] = 2; // Fill the lookup table in bottom-up manner for (int i = 3; i <= n; i++) lookup[i] = lookup[i - 1] + lookup[i - 2] + lookup[i - 3]; return lookup[n]; } // main function int main(void) { int n = 4; printf("Total ways to reach the %d'th stair are %d", n, totalWays(n)); return 0; } |

`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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <stdio.h> // DP function to find total ways to reach the n'th stair from bottom // when a person is allowed to climb either 1 or 2 or 3 stairs at a time int totalWays(int n) { // base case: 1 way (with no steps) int a = 1; // There is only 1 way to reach the 1st stair int b = 1; // There are 2 ways to reach the 2nd stair int c = 2; for (int i = 3; i <= n; i++) { int result = a + b + c; a = b; b = c; c = result; } return c; } // main function int main(void) { int n = 4; printf("Total ways to reach the %d'th stair are %d", n, totalWays(n)); return 0; } |

`Output:`

Total ways to reach the 4’th stair are 7

**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