A frog on a number line records how many distinct routes reach stone n when every hop advances by 1, 2 or 3 stones, but the frog's log uses an unusual convention: H(0) = 0, H(1) = 0, H(2) = 1, and for n >= 3, H(n) = H(n-1) + H(n-2) + H(n-3). Write hop_sequence(n) returning H(n).
Examples
Input: n = 6
Output: 7
Explanation: H(3) = 1, H(4) = 2, H(5) = 4, H(6) = 7.
Input: n = 0
Output: 0
Constraints
0 <= n <= 1500; results are big integers, which Python handles.- A memoised recursion uses at most
nstack levels, under the ~3000 limit.
Goals
- Define a sequence by a recurrence with three base cases
- Memoise so linear recursion does not explode into a tree
- Keep recursion depth linear and under the interpreter limit