In this tutorial, we will be understanding a very interesting problem known as The Ladders Problem. Let us first understand what do we want to achieve in this problem.
Understanding the Ladders Problem
In the problem we are given two inputs, one is the number of steps and the other is the maximum number of steps that can be taken by a person at a time.
For instance, if the maximum number of steps = 3. A person can take either 1 step, 2 steps, or 3 steps at a particular time.
We need to count all the ways the person can reach the top of the ladder by either taking 1, 2, or 3 steps at a time.
Solution to the Ladders Problem
Now the problem can be solved using normal looping and if-else statements. But a better approach is to follow the Recursion approach. If you are unaware of how Recursion works, I recommend you to read the tutorial mentioned below.
Read more about Recursion: Recursion in Python
In order to solve this problem, we will be looking for the smallest problems i.e. for n = 1 to n = n. Let’s consider the maximum number of steps can be 3.
The case is illustrated in the figure below.
Now let’s look at the code implementation of the ladders problem.
Code Implementation of the Ladders Problem in Python
Here we are computing the number of ways for k maximum steps. So we will be computing the values in order (n-1),(n-2),(n-3) and so on till (n-k).
And in the end, we will be summing up all the values obtained and return the final answer. The code implementation of the same is given below.
def count_no_ways(n,k):
if(n<0):
return 0
# already on top
if(n==0):
return 1
if(n<3):
return n
ans = 0
for i in range(1,k+1):
ans+=count_no_ways(n-i,k)
return ans
n = int(input())
k = int(input())
print(count_no_ways(n,k))
Output:
17
17
65536
I hope you are clear with the concept of recursion used in the ladders problem and will be able to implement the same on your own.
Thank you for reading! Happy learning! 😇