Implementing the Monkey Jumping on Stairs Problem in Python

The “Monkey Jumping on Stairs” problem is a classic dynamic programming problem that can be solved efficiently using Python. The problem statement is as follows: A monkey is trying to climb a staircase with n stairs. It can climb 1 or 2 stairs at a time. How many different ways can the monkey climb to the top of the stairs?

Understanding the Problem

Let’s consider a simple example to understand the problem better. Suppose there are 3 stairs. The monkey can reach the top in the following ways:

1. Climb 1 stair, then climb 1 stair again, and finally, climb 1 stair to reach the top. (1-1-1)
2. Climb 2 stairs first and then climb 1 stair to reach the top. (2-1)
3. Climb 1 stair first and then climb 2 stairs to reach the top. (1-2)

So, for 3 stairs, there are 3 ways for the monkey to climb.

Solving the Problem with Python

To solve this problem, we can use a dynamic programming approach. We’ll create an array dp where dp[i] represents the number of ways the monkey can reach the ith stair.

Here’s the Python code that implements this solution:

pythondef monkey_jump(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 2

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

# Example usage
stairs = 5
print(f"Number of ways the monkey can climb {stairs} stairs: {monkey_jump(stairs)}")

In this code, we initialize dp[1] and dp[2] to 1 and 2, respectively, as there’s only one way to climb 1 stair and two ways to climb 2 stairs. Then, for each subsequent stair i (from 3 to n), we calculate the number of ways by adding the number of ways to reach the previous two stairs (dp[i - 1] and dp[i - 2]).
Conclusion
The “Monkey Jumping on Stairs” problem is a great example of how dynamic programming can be used to solve optimization problems efficiently. By breaking down the problem into smaller subproblems and storing their solutions, we can avoid redundant calculations and achieve a time complexity of O(n) for this problem.