Norway


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:

 

Download   Run Code

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.

 

Download   Run Code

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:

 

Download   Run Code

Output:

Total ways to reach the 4’th stair with at-most 3 steps are 7

 
1 Star  - rating on - Find total ways to reach the n’th stair with at-most m steps2 Stars  - rating on - Find total ways to reach the n’th stair with at-most m steps3 Stars  - rating on - Find total ways to reach the n’th stair with at-most m steps4 Stars  - rating on - Find total ways to reach the n’th stair with at-most m steps5 Stars  - rating on - Find total ways to reach the n’th stair with at-most m steps (1 votes, average: 5.00 out of 5)

- loading - Find total ways to reach the n’th stair with at-most m stepsLoading…

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 🙂
 



Source link

LEAVE A REPLY

Please enter your comment!
Please enter your name here