The "Count All Possible Routes" problem asks you to determine the number of different routes you can take from a start city to a finish city, given a list of city locations and a limited amount of fuel.
Each route is a sequence of moves between cities, where traveling from city i to city j costs abs(locations[i] - locations[j]) units of fuel. You may visit the same city multiple times, including the start and finish cities, as long as you have enough fuel for each move. The goal is to count the total number of possible routes from start to finish (including routes that visit the finish city more than once), using at most the given amount of fuel.
Key constraints:
10^9 + 7.
At first glance, this problem seems to require exploring all possible paths from start to finish within the fuel limit. A brute-force approach would be to recursively try every possible move from each city, keeping track of the remaining fuel, and counting every time we reach the finish city.
However, this naive approach quickly becomes infeasible: the number of possible paths grows exponentially with the number of cities and the amount of fuel. Many of these paths revisit the same city with the same remaining fuel, leading to repeated calculations.
To optimize, we notice that the state of our problem is entirely determined by our current city and the amount of fuel left. If we have already calculated the number of routes from a given city with a given amount of fuel, we can store (memoize) that result and reuse it later, dramatically reducing redundant work.
We'll use a recursive depth-first search (DFS) with memoization (also known as dynamic programming with top-down recursion) to efficiently count all possible routes. Here's how the algorithm works:
curr and the remaining fuel.
finish city, we count this as a valid route (even if we have fuel left).10^9 + 7.
This approach ensures that each unique (city, fuel) combination is only computed once, leading to significant performance gains.
Sample Input:
locations = [2, 3, 6, 8, 4]
start = 1 (city at position 3)
finish = 3 (city at position 8)
fuel = 5
Step-by-step trace:
For this example, the answer is 4: there are 4 different possible routes from city 1 to city 3 with at most 5 fuel.
Brute-force Approach:
The brute-force method explores all possible paths, leading to exponential time complexity: O(N^F), where N is the number of cities and F is the fuel. This is not feasible for large inputs.
Optimized Approach (DP with Memoization):
This makes the solution efficient enough for the problem's constraints.
The "Count All Possible Routes" problem is a classic example of dynamic programming with overlapping subproblems, where naive recursion would be far too slow. By recognizing that the state is determined by (current city, remaining fuel), we can use memoization to efficiently count all possible valid routes. The solution demonstrates the power of DP in reducing exponential problems to polynomial time, and highlights the importance of caching repeated computations.
from functools import lru_cache
class Solution:
def countRoutes(self, locations, start, finish, fuel):
MOD = 10**9 + 7
n = len(locations)
@lru_cache(None)
def dfs(curr, fuel_left):
if fuel_left < 0:
return 0
res = 1 if curr == finish else 0
for next_city in range(n):
if next_city != curr:
cost = abs(locations[curr] - locations[next_city])
if fuel_left - cost >= 0:
res = (res + dfs(next_city, fuel_left - cost)) % MOD
return res
return dfs(start, fuel)
class Solution {
public:
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
const int MOD = 1e9 + 7;
int n = locations.size();
vector<vector<int>> dp(n, vector<int>(fuel + 1, -1));
function<int(int, int)> dfs = [&](int curr, int fuel_left) {
if (fuel_left < 0) return 0;
if (dp[curr][fuel_left] != -1) return dp[curr][fuel_left];
int res = (curr == finish) ? 1 : 0;
for (int next = 0; next < n; ++next) {
if (next != curr) {
int cost = abs(locations[curr] - locations[next]);
if (fuel_left - cost >= 0) {
res = (res + dfs(next, fuel_left - cost)) % MOD;
}
}
}
return dp[curr][fuel_left] = res;
};
return dfs(start, fuel);
}
};
class Solution {
private static final int MOD = 1_000_000_007;
int[][] dp;
int[] locations;
int finish;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
int n = locations.length;
this.locations = locations;
this.finish = finish;
dp = new int[n][fuel + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= fuel; j++) {
dp[i][j] = -1;
}
}
return dfs(start, fuel);
}
private int dfs(int curr, int fuel_left) {
if (fuel_left < 0) return 0;
if (dp[curr][fuel_left] != -1) return dp[curr][fuel_left];
int res = (curr == finish) ? 1 : 0;
for (int next = 0; next < locations.length; next++) {
if (next != curr) {
int cost = Math.abs(locations[curr] - locations[next]);
if (fuel_left - cost >= 0) {
res = (res + dfs(next, fuel_left - cost)) % MOD;
}
}
}
dp[curr][fuel_left] = res;
return res;
}
}
var countRoutes = function(locations, start, finish, fuel) {
const MOD = 1e9 + 7;
const n = locations.length;
const memo = Array.from({length: n}, () => Array(fuel + 1).fill(-1));
function dfs(curr, fuel_left) {
if (fuel_left < 0) return 0;
if (memo[curr][fuel_left] !== -1) return memo[curr][fuel_left];
let res = (curr === finish) ? 1 : 0;
for (let next = 0; next < n; ++next) {
if (next !== curr) {
const cost = Math.abs(locations[curr] - locations[next]);
if (fuel_left - cost >= 0) {
res = (res + dfs(next, fuel_left - cost)) % MOD;
}
}
}
memo[curr][fuel_left] = res;
return res;
}
return dfs(start, fuel);
};