{x}
blog image

Count All Possible Routes

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 <= 100
  • 1 <= locations[i] <= 109
  • All integers in locations are distinct.
  • 0 <= start, finish < locations.length
  • 1 <= fuel <= 200

1575. Count All Possible Routes

This problem asks to count the number of possible routes from a starting city to a finishing city, given a limited amount of fuel and the distances between cities. The key constraint is that fuel cannot become negative at any point.

Approach: Dynamic Programming with Memoization (or Top-Down DP)

The most efficient approach is dynamic programming with memoization. This avoids redundant calculations by storing the results of subproblems.

State:

  • dp[i][fuel] represents the number of routes from city i to the finish city with fuel units of fuel remaining.

Base Case:

  • dp[finish][fuel] = 1 for all fuel (reaching the finish city is always a valid route).
  • dp[i][fuel] = 0 if fuel < abs(locations[i] - locations[finish]) (not enough fuel to reach the finish city directly).

Recursive Relation:

For each city i and fuel level fuel:

dp[i][fuel] = Σ dp[j][fuel - abs(locations[i] - locations[j])]  for all j ≠ i, and fuel - abs(locations[i] - locations[j]) >= 0

This means the number of routes from city i with fuel is the sum of routes from all other cities j, provided there's enough fuel to travel from i to j.

Algorithm:

  1. Initialization: Create a DP table dp of size (n, fuel + 1) and initialize the base cases.
  2. Iteration: Iterate through the fuel levels from 0 to fuel. For each fuel level, iterate through cities. Compute dp[i][fuel] using the recursive relation. The order matters; we must process lower fuel levels before higher ones.
  3. Result: dp[start][fuel] contains the number of routes from the starting city with the initial fuel.

Time and Space Complexity Analysis

  • Time Complexity: O(N2 * Fuel), where N is the number of cities and Fuel is the maximum fuel available. We iterate through cities and fuel levels nested three times.
  • Space Complexity: O(N * Fuel). This is the size of the DP table.

Code Implementation (Python)

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        n = len(locations)
        mod = 10**9 + 7
        dp = [[0] * (fuel + 1) for _ in range(n)]
 
        for f in range(fuel + 1):
            dp[finish][f] = 1  # Base case
 
        for f in range(fuel + 1):
            for i in range(n):
                if f < abs(locations[i] - locations[finish]):
                    continue #Not enough fuel to reach finish from city i
                for j in range(n):
                    if i != j and f >= abs(locations[i] - locations[j]):
                        dp[i][f] = (dp[i][f] + dp[j][f - abs(locations[i] - locations[j])]) % mod
        
        return dp[start][fuel]

Code Implementation (Java)

class Solution {
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        int mod = (int)1e9 + 7;
        int[][] dp = new int[n][fuel + 1];
 
        for (int f = 0; f <= fuel; f++) {
            dp[finish][f] = 1; // Base case
        }
 
        for (int f = 0; f <= fuel; f++) {
            for (int i = 0; i < n; i++) {
                if (f < Math.abs(locations[i] - locations[finish])) continue;
                for (int j = 0; j < n; j++) {
                    if (i != j && f >= Math.abs(locations[i] - locations[j])) {
                        dp[i][f] = (dp[i][f] + dp[j][f - Math.abs(locations[i] - locations[j])]) % mod;
                    }
                }
            }
        }
        return dp[start][fuel];
    }
}

Other languages (C++, Javascript, etc.) would follow a similar structure, adapting the syntax accordingly. The core logic of the dynamic programming solution remains the same across all languages.