How Many Ways Can a Monkey Reach the Top? DP Solution for 1‑step or 3‑step Jumps

Problem Statement

A monkey wants to climb from the foot of a mountain to the summit, passing a staircase with n steps. At each move the monkey can jump either 1 step or 3 steps. Determine how many different jumping sequences can reach the top.

Input

One integer n where 0 ≤ n ≤ 50, representing the number of steps.

Output

An integer indicating the total number of possible jumping ways.

Examples

Input: 50 → Output: 122106097 Input: 3 → Output:

2

Solution Idea

The problem is identical to LeetCode 70 (Climbing Stairs) except the allowed jumps are 1 and 3 instead of 1 and 2.

We use a classic dynamic‑programming (DP) approach.

DP array definition : dp[i] stores the number of ways to reach step i.

Transition formula : To reach step i, the monkey could have come from step i‑1 (a 1‑step jump) or from step i‑3 (a 3‑step jump). Hence dp[i] = dp[i-1] + dp[i-3] Initialization : dp[0] = 1 – the starting position has one trivial way. dp[1] = 1 – only a single 1‑step jump. dp[2] = 1 – the only way is two consecutive 1‑step jumps (the 3‑step jump is impossible).

Reference Implementation (Python)

# Problem: 2023Q1A – Monkey Climbing Stairs
n = int(input())
# dp[i] = number of ways to reach step i
dp = [0] * (n + 1)
# base cases
dp[0] = dp[1] = dp[2] = 1
for i in range(3, n + 1):
    dp[i] = dp[i-1] + dp[i-3]
print(dp[n])

Complexity Analysis

Time complexity: O(N) – each step is processed once.

Space complexity: O(N) – the DP array of size n+1 is stored.