River Hop Routes
Easy · dynamic programming
A river has stepping stones numbered 0 to n in a straight line. You start on stone 0 and want to reach stone n.
A hop moves you forward by exactly one of the lengths in the list hops. You may use any length as often as you like. Some stones are cracked: you may never land on them. You can always stand on stone 0 and stone n.
Two routes are different if the stones you land on are different, in order. Return the number of routes from stone 0 to stone n, modulo 10^9 + 7. If there is no route, return 0.
Examples
Example 1
Input: n = 4, hops = [1, 2], cracked = []
Output: 5
The routes are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Example 2
Input: n = 5, hops = [1, 2], cracked = [2]
Output: 2
Stone 2 is off limits, so you must start with a hop of 1 and then a hop of 2 to stone 3. From there you can finish with 1+1 or with 2.
Example 3
Input: n = 3, hops = [2], cracked = []
Output: 0
Hops of 2 only land on even stones, so stone 3 can never be reached.
Constraints
- 1 <= n <= 1000
- 1 <= len(hops) <= 1000
- 1 <= hops[i] <= 1000, and all values in hops are different
- 0 <= len(cracked) <= n - 1
- 1 <= cracked[i] <= n - 1, and all values in cracked are different