Hop One or Three
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
0 <= n <= 40
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- N-th Tribonacci NumberBeginner
- Paving With Colored SlabsBeginner
- Pell NumbersBeginner
- Savings With InterestBeginner
- Stacked CansBeginner
- Sum of the Last kBeginner
- Take One, Two or ThreeBeginner
- Three Button CalculatorBeginner