#1575

Count All Possible Routes

expert · 1080 · lc hard +32 · verified · 64.9% accepted · 1,675 likes · top 69%

Description

You are given an array locations of city positions along a line, a start city, a finish city, and an initial fuel amount. Moving from city i to city j costs |locations[i] - locations[j]| fuel. You may revisit cities but fuel cannot go negative. Count all distinct routes from start to finish across any number of intermediate stops. Return the result modulo 10⁹ + 7.

Example 1:

Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5

Output: 4

Explanation: The following are all possible routes, each uses 5 units of fuel:

1 -> 3

1 -> 2 -> 3

1 -> 4 -> 3

1 -> 4 -> 2 -> 3

Example 2:

Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6

Output: 5

Explanation: The following are all possible routes:

1 -> 0, used fuel = 1

1 -> 2 -> 0, used fuel = 5

1 -> 2 -> 1 -> 0, used fuel = 5

1 -> 0 -> 1 -> 0, used fuel = 3

1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5

Example 3:

Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3

Output: 0

Explanation: It is impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.

Code

1

2

3

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int: