FunctionRacerProblemsRace

Hops Over Wet Steps

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

A staircase has steps numbered from 0, where you stand, up to top. Each hop takes you up by one of the sizes in hops, and you may reuse a size as often as you like. The steps listed in wet are slippery and you must never land on them; every wet step lies strictly between 0 and top. Return the number of different hop sequences that land exactly on step top. Two sequences are different if they differ at any hop. When top = 0 the only route is to make no hops at all, so return 1.

Example 1

top 4
hops [1,2]
wet [2]
returns 1

Only the sequence 1, 2, 1 avoids step 2: it lands on steps 1, 3 and 4.

Example 2

top 5
hops [2,3]
wet []
returns 2

The two routes are 2 then 3, and 3 then 2.

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