# Count All Possible Routes
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-all-possible-routes)
Canonical: https://scaleengineer.com/dsa/problems/count-all-possible-routes
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem into a recursive function. We define a function `solve(currentCity, remainingFuel)` that explores all possible next moves from `currentCity`. For each valid move to a city `j`, it makes a recursive call with the updated fuel. The base case is when we are at the `finish` city, which counts as one valid route.
**Time:** O(n^fuel), where n is the number of locations. In the worst case, from each city, we can branch to `n-1` other cities. The recursion depth can be up to `fuel` (since the minimum fuel cost is 1 for distinct locations), leading to an exponential number of calls. · **Space:** O(fuel). The space complexity is determined by the maximum depth of the recursion stack, which is proportional to the initial fuel.
**Pros:** Simple to understand and implement as it directly models the problem's state transitions.; Requires minimal data structures.
**Cons:** Extremely inefficient due to an exponential number of redundant calculations.; Will result in a 'Time Limit Exceeded' error for all but the smallest inputs.
### Explanation
We define a recursive helper function, say `solve(curr, fuelLeft)`, that calculates the number of ways to reach the `finish` city starting from `curr` with `fuelLeft` amount of fuel. If `fuelLeft` becomes negative, it signifies an invalid path, and the function returns 0. We initialize a variable `ans`. If `curr` is the `finish` city, we set `ans` to 1, as this represents a valid route that ends at this point. Then, we iterate through all possible next cities `nextCity`. For each `nextCity` that is different from `curr`, we calculate the `fuelNeeded`. If `fuelLeft >= fuelNeeded`, we can make this move. We then recursively call `solve(nextCity, fuelLeft - fuelNeeded)` and add the returned value to `ans`. To handle potentially large results, all additions are performed modulo `10^9 + 7`. The process starts with an initial call to `solve(start, fuel)`. This method is very slow because it repeatedly recomputes the results for the same state (`curr`, `fuelLeft`), leading to an exponential time complexity.

```java
class Solution {
    int finish;
    int[] locations;
    int MOD = 1_000_000_007;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        this.locations = locations;
        this.finish = finish;
        return solve(start, fuel);
    }

    private int solve(int currentCity, int remainingFuel) {
        if (remainingFuel < 0) {
            return 0;
        }

        long ans = 0;
        if (currentCity == finish) {
            ans = 1;
        }

        for (int nextCity = 0; nextCity < locations.length; nextCity++) {
            if (nextCity == currentCity) {
                continue;
            }
            int cost = Math.abs(locations[currentCity] - locations[nextCity]);
            if (remainingFuel >= cost) {
                ans = (ans + solve(nextCity, remainingFuel - cost)) % MOD;
            }
        }

        return (int) ans;
    }
}
```
### Algorithm
1. Define a recursive function `solve(currentCity, remainingFuel)`.
2. Initialize a counter `count` to 0. If `currentCity` is the `finish` city, set `count` to 1 to account for the route ending at the destination.
3. Iterate through all possible next cities `j` from `0` to `n-1`.
4. If `j` is the same as `currentCity`, skip to the next city.
5. Calculate the fuel `cost` required to travel from `currentCity` to `j`: `cost = |locations[currentCity] - locations[j]|`.
6. If `remainingFuel` is sufficient for the travel (i.e., `remainingFuel >= cost`):
   - Make a recursive call `solve(j, remainingFuel - cost)` to find the number of routes from city `j`.
   - Add the result of the recursive call to `count`.
   - Apply modulo `10^9 + 7` to `count` to prevent overflow.
7. Return the total `count`.
8. The main function initiates the process by calling `solve(start, fuel)`.

## Top-Down Dynamic Programming (Memoization)
This approach optimizes the brute-force recursion by using memoization to avoid recomputing results for the same subproblems. We use a 2D array, `memo[city][fuel]`, to store the result of `solve(city, fuel)`. This is a classic top-down dynamic programming technique.
**Time:** O(n^2 * fuel), where `n` is the number of locations. There are `n * fuel` possible states for `(city, fuel)`. For each state, we iterate through `n` possible next cities. · **Space:** O(n * fuel). This is for the memoization table. The recursion stack depth also contributes up to O(fuel).
**Pros:** Much more efficient than brute-force and is fast enough for the given constraints.; The logic is a natural extension of the recursive solution, making it relatively easy to implement.
**Cons:** Requires significant memory for the memoization table, O(n * fuel).; Can still lead to a stack overflow error for very deep recursion, although the `fuel` constraint (<= 200) makes this unlikely.
### Explanation
The core idea is to store the results of subproblems defined by the state `(currentCity, remainingFuel)` to avoid redundant calculations. We create a 2D array `memo` of size `locations.length` by `fuel + 1` and initialize it with a special value (e.g., `null` or -1) to mark states as uncomputed. The recursive function `solve(currentCity, remainingFuel)` first checks if `memo[currentCity][remainingFuel]` has been computed. If it has, the stored value is returned immediately. Otherwise, it computes the value as in the brute-force approach by summing up the results from all valid next moves. Before returning, the computed value is stored in `memo[currentCity][remainingFuel]` for future lookups. This optimization drastically reduces the time complexity by ensuring each state is computed only once.

```java
import java.util.Arrays;

class Solution {
    int finish;
    int[] locations;
    int MOD = 1_000_000_007;
    Integer[][] memo;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        this.locations = locations;
        this.finish = finish;
        this.memo = new Integer[locations.length][fuel + 1];
        return solve(start, fuel);
    }

    private int solve(int currentCity, int remainingFuel) {
        if (remainingFuel < 0) {
            return 0;
        }
        if (memo[currentCity][remainingFuel] != null) {
            return memo[currentCity][remainingFuel];
        }

        long ans = 0;
        if (currentCity == finish) {
            ans = 1;
        }

        for (int nextCity = 0; nextCity < locations.length; nextCity++) {
            if (nextCity == currentCity) {
                continue;
            }
            int cost = Math.abs(locations[currentCity] - locations[nextCity]);
            if (remainingFuel >= cost) {
                ans = (ans + solve(nextCity, remainingFuel - cost)) % MOD;
            }
        }

        return memo[currentCity][remainingFuel] = (int) ans;
    }
}
```
### Algorithm
1. Create a 2D memoization table `memo[n][fuel+1]` and initialize all its entries to a value indicating they haven't been computed (e.g., -1 or null).
2. Define a recursive function `solve(currentCity, remainingFuel)`.
3. If `remainingFuel` is negative, return 0.
4. Check if `memo[currentCity][remainingFuel]` has a computed value. If so, return it.
5. Initialize a counter `count`. If `currentCity == finish`, set `count = 1`.
6. Iterate through all cities `j` from `0` to `n-1`.
7. If `j == currentCity`, skip.
8. Calculate `cost = |locations[currentCity] - locations[j]|`.
9. If `remainingFuel >= cost`, recursively call `solve(j, remainingFuel - cost)` and add the result to `count`, taking the modulo `10^9 + 7`.
10. Store the final `count` in `memo[currentCity][remainingFuel]` before returning it.
11. The main function calls `solve(start, fuel)` to get the final answer.

## Bottom-Up Dynamic Programming
This approach, also known as tabulation, solves the problem iteratively. We build up the solution for larger amounts of fuel based on the solutions for smaller amounts. This avoids recursion overhead and can be slightly more efficient in practice. We define `dp[f][i]` as the number of ways to reach city `i` from the `start` city using exactly `f` fuel.
**Time:** O(n^2 * fuel). We have three nested loops iterating up to `fuel`, `n`, and `n` respectively. · **Space:** O(n * fuel) for the DP table.
**Pros:** Avoids recursion overhead, which can lead to a small performance improvement and prevents potential stack overflow issues.; Iterative solutions can sometimes be easier to analyze and optimize further.
**Cons:** The DP state and transitions can be less intuitive to formulate compared to the top-down approach.; Requires O(n * fuel) memory, similar to the memoization approach.
### Explanation
We use a 2D DP table, `dp[fuel + 1][n]`, where `dp[f][i]` stores the number of ways to reach city `i` from the `start` city using exactly `f` units of fuel. We initialize `dp[0][start] = 1` because there is one way to be at the start city with zero fuel consumed (i.e., we start there). We then iterate through fuel `f` from 1 up to the given `fuel`. For each amount of fuel `f`, we calculate the number of ways to reach every city `i`. To reach city `i` with `f` fuel, we must have come from some other city `j` with `f - cost` fuel, where `cost` is the fuel needed to travel from `j` to `i`. So, we sum up `dp[f - cost][j]` for all possible previous cities `j`. The final answer is the sum of `dp[f][finish]` for all `f` from 0 to `fuel`, as we can arrive at the finish city with any amount of fuel consumed up to the initial `fuel`.

```java
class Solution {
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        int MOD = 1_000_000_007;
        long[][] dp = new long[fuel + 1][n];

        // dp[f][i] = number of ways to reach city i from start using exactly f fuel
        dp[0][start] = 1;

        for (int f = 1; f <= fuel; f++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) {
                        continue;
                    }
                    int cost = Math.abs(locations[i] - locations[j]);
                    if (f >= cost) {
                        dp[f][i] = (dp[f][i] + dp[f - cost][j]) % MOD;
                    }
                }
            }
        }

        long totalRoutes = 0;
        for (int f = 0; f <= fuel; f++) {
            totalRoutes = (totalRoutes + dp[f][finish]) % MOD;
        }

        return (int) totalRoutes;
    }
}
```
### Algorithm
1. Let `n` be the number of locations.
2. Create a 2D DP table `dp[fuel + 1][n]`. `dp[f][i]` will store the number of ways to reach city `i` from the `start` city using exactly `f` fuel.
3. Initialize the `dp` table with 0s. Set `dp[0][start] = 1`, as there is one way to be at the start city with zero fuel used (the starting point).
4. Iterate through the fuel amount `f` from `1` to `fuel`.
5.   Inside this loop, iterate through each city `i` from `0` to `n-1` (the destination city of a move).
6.     Inside this loop, iterate through each city `j` from `0` to `n-1` (the source city of a move).
7.       If `i == j`, continue.
8.       Calculate the `cost` to move from `j` to `i`: `cost = |locations[i] - locations[j]|`.
9.       If `f >= cost`, it means a move from `j` to `i` is possible. Update `dp[f][i]` by adding the number of ways to reach city `j` with `f - cost` fuel: `dp[f][i] = (dp[f][i] + dp[f - cost][j]) % MOD`.
10. After filling the DP table, calculate the total number of routes to the `finish` city. Initialize `totalRoutes = 0`.
11. Iterate `f` from `0` to `fuel` and add `dp[f][finish]` to `totalRoutes`, taking the modulo at each step.
12. Return `totalRoutes`.

# Solutions
### Java

```java
class Solution {
private
  int[] locations;
private
  int finish;
private
  int n;
private
  Integer[][] f;
private
  final int mod = (int)1 e9 + 7;
public
  int countRoutes(int[] locations, int start, int finish, int fuel) {
    n = locations.length;
    this.locations = locations;
    this.finish = finish;
    f = new Integer[n][fuel + 1];
    return dfs(start, fuel);
  }
private
  int dfs(int i, int k) {
    if (k < Math.abs(locations[i] - locations[finish])) {
      return 0;
    }
    if (f[i][k] != null) {
      return f[i][k];
    }
    int ans = i == finish ? 1 : 0;
    for (int j = 0; j < n; ++j) {
      if (j != i) {
        ans = (ans + dfs(j, k - Math.abs(locations[i] - locations[j]))) % mod;
      }
    }
    return f[i][k] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countRoutes(vector<int> &locations, int start, int finish, int fuel) {
    int n = locations.size();
    int f[n][fuel + 1];
    memset(f, -1, sizeof(f));
    const int mod = 1e9 + 7;
    function<int(int, int)> dfs = [&](int i, int k) -> int {
      if (k < abs(locations[i] - locations[finish])) {
        return 0;
      }
      if (f[i][k] != -1) {
        return f[i][k];
      }
      int ans = i == finish;
      for (int j = 0; j < n; ++j) {
        if (j != i) {
          ans = (ans + dfs(j, k - abs(locations[i] - locations[j]))) % mod;
        }
      }
      return f[i][k] = ans;
    };
    return dfs(start, fuel);
  }
};

```

### Python

```python
class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int: @ cache def dfs(i: int, k: int) -> int: if k < abs(locations[i] - locations[finish]): return 0 ans = int(i == finish) for j, x in enumerate(locations): if j != i: ans = (ans + dfs(j, k - abs(locations[i] - x))) % mod return ans mod = 10 ** 9 + 7 return dfs(start, fuel)

```