FunctionRacerProblemsRace

No Double Leaps

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

You climb a ladder from rung 0 to rung top. Each move is either a step, which takes you up one rung, or a leap, which takes you up two rungs. You are never allowed to make two leaps in a row, and the rungs listed in loose are broken, so you may not stop on them; every loose rung lies strictly between 0 and top. Return the number of different move sequences that end exactly on rung top. If top = 0, return 1 for the empty sequence.

Example 1

top 4
loose []
returns 4

The sequences are step-step-step-step, step-step-leap, step-leap-step and leap-step-step; leap-leap is forbidden.

Example 2

top 4
loose [2]
returns 1

Only step, leap, step avoids rung 2: it stops on rungs 1, 3 and 4.

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