#24Rabbit Path— 1, 3, or 5 Jumps
EasyDynamic ProgrammingRecursionMemoizationArrayFibonacci-like
A rabbit is crossing a path containing n positions. It starts at position 0 and needs to reach position n. At each move, the rabbit can jump forward by exactly 1, 3, or 5 positions. Determine the number of distinct ways the rabbit can reach exactly position n. Two paths are considered different if they contain a different sequence of jumps.
Examples
Example 1
Input: n = 5
Output: 5
Explanation: 1 + 1 + 1 + 1 + 1, 1 + 1 + 3, 1 + 3 + 1, 3 + 1 + 1, 5
Example 2
Input: n = 6
Output: 8
Explanation: 1 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 3, 1 + 1 + 3 + 1, 1 + 3 + 1 + 1, 3 + 1 + 1 + 1, 1 + 5, 5 + 1, 3 + 3,
Example 3
Input: n = 8
Output: 19
Explanation: --
Constraints
- 1 ≤ n ≤ 35
- The rabbit can jump only 1, 3, or 5 positions.
- The answer fits within a signed 32-bit integer.