You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.
At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.
Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).
Return the count of all possible routes from start to finish. Since the answer may be too large, return it modulo 109 + 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.
Constraints:
2 <= locations.length <= 1001 <= locations[i] <= 109locations are distinct.0 <= start, finish < locations.length1 <= fuel <= 200This approach involves using dynamic programming to keep track of the number of ways to reach the target city with the available fuel. We will define a DP table where dp[i][f] represents the number of ways to start from city i with f units of fuel left and reach the target city. We recursively fill this table while considering moves to any other city and subtracting the appropriate fuel cost for that move. The result will be stored in the dp[start][fuel] after exploring all possible routes.
The C solution uses a top-down dynamic programming approach with memoization. It initializes a 2D array (dp) to store the number of routes. The recursive function explores from the current city to possible destinations, decrementing the fuel and checking if it reaches the finish city. Modulo operation by 10^9 + 7 is applied to avoid overflow.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * fuel * n), where n is the number of cities. This can be reduced using better states or pruning.
Space Complexity: O(n * fuel) for the dp table.
In this approach, a depth-first search (DFS) is implemented to explore possible routes from the start to the finish city. Each travel option is a branch in the DFS tree, where the algorithm explores each choice of stopping at a different city until it no longer has fuel. The recursion keeps track of current fuel and updates the count whenever it reaches the finish city with valid fuel.
The C solution provides a direct recursive DFS approach without memoizing results. This traverses all possible pathways considering each move and updates the route count if successful. Uses modulo for result consistency.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^fuel) without pruning, given recursive branching per city. This complexity is potentially high without memoization.
Space Complexity: O(fuel) due to recursive call stack depth.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memoization | Time Complexity: O(n * fuel * n), where n is the number of cities. This can be reduced using better states or pruning. |
| Recursive Depth-First Search | Time Complexity: O(n^fuel) without pruning, given recursive branching per city. This complexity is potentially high without memoization. |
Unique Paths - Dynamic Programming - Leetcode 62 • NeetCode • 157,703 views views
Watch 9 more video solutions →Practice Count All Possible Routes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor