No Double Leaps
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
0 <= top <= 400 <= len(loose) <= 10, the rungs are distinct and1 <= loose[i] <= top - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- One Forgiven DayMedium
- Paint the FenceMedium
- Shared Subsequence LengthMedium
- Trading With Rest DaysMedium
- Unique Binary Search TreesMedium
- Unique Grid PathsMedium
- Ways to Make ChangeMedium
- At Most K TradesHard