  Given a stair case, find number of ways to reach the n’th stair from bottom of the stair when a person is only allowed to take at-most m at a time.

For example,

Input: n = 3, m = 2
Output: Total ways to reach the 3’rd stair with at-most 2 steps are 3

1 step  + 1 step  + 1 step
1 step  + 2 steps
2 steps + 1 step

Input: n = 4, m = 3
Output: Total ways to reach the 4’th stair with at-most 3 steps 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

In previous post, we have discussed how to get number of ways to reach the n'th stair from bottom of the stair when a person is allowed to take at-most 3 steps at a time. In this post, we will extend the solution for at-most m steps.

For a maximum of 3 steps at a time, we have came up with the recurrence relation T(n):

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

For at-most m steps, the recurrence relation T(n) can be written as following:

T(n) = T(n-1) + T(n-2) + ... T(n-m)

i.e. we can reach the n'th stair from either (n-1)'th stair, (n-2)'th stair, (n-3)'th. … (n-m)'th stair. Here’s a C program that implements the above recurrence:

Output:

Total ways to reach the 4’th stair with at-most 3 steps 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 bring down the time complexity to O(mn). This can be done in either top-down or bottom-up fashion:

### 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 with at-most 3 steps 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 with at-most 3 steps are 7     (1 votes, average: 5.00 out of 5) Loading…