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 andT(0) = 1, T(1) = 1, and T(2) = 2`

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

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

Like us? Please spread the word and help us grow. Happy coding 🙂

more link ADS

Smart Retail, Smart Agriculture, Smart supply Chain, Smart Health, Smart energy, Smart City

Blockchain, bitcoin, ethereum, blockchain technology, cryptocurrencies

Information Security, latest Hacking News, Cyber Security, Network Sec

Information Security, latest Hacking News, Cyber Security, Network Security

Blog! Development Software and Application Mobile

Development apps, Android, Ios anh Tranning IT, data center, hacking

Car News, Reviews, Pricing for New & Used Cars, car reviews and news, concept cars

Travel Blog is a unique free online travel diary for travellers across the world.