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

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

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

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

If the answers is incorrect or not given, you can answer the above question in the comment box. If the answers is incorrect or not given, you can answer the above question in the comment box.