FunctionRacerProblemsRace

Hop One or Three

BeginnerDynamic programmingPython, JavaScript, TypeScript, Java, C++

A frog sits on stone 0 of a row of stones and wants to reach stone n. With each hop it moves forward by exactly 1 stone or by exactly 3 stones.

Return the number of different ways to reach stone n. Two ways are different if they are not the same series of hops. There is one way to reach stone 0: do nothing.

Example 1

n 4
returns 3

1+1+1+1, then 1+3 and 3+1.

Example 2

n 3
returns 2

Three single hops, or one hop of three.

Example 3

n 2
returns 1

Only two single hops work.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems