Count All Possible Routes
Problem
You are given an array locations of distinct integers (the position of each city), plus integers start, finish, and fuel. Beginning at city start with fuel units, you may repeatedly drive from your current city i to any different city j, which burns abs(locations[i] − locations[j]) fuel. You may revisit cities and may pass through finish without stopping. Count how many distinct routes end at city finish while fuel never goes negative. Return the count modulo 109+7.
locations = [2, 3, 6, 8, 4], start = 1, finish = 3, fuel = 54def count_routes(locations, start, finish, fuel):
MOD = 10**9 + 7
n = len(locations)
from functools import lru_cache
@lru_cache(None)
def f(city, gas):
res = 1 if city == finish else 0
for j in range(n):
if j != city:
cost = abs(locations[city] - locations[j])
if cost <= gas:
res += f(j, gas - cost)
return res % MOD
return f(start, fuel)function countRoutes(locations, start, finish, fuel) {
const MOD = 1e9 + 7, n = locations.length;
const memo = new Map();
function f(city, gas) {
const key = city + ',' + gas;
if (memo.has(key)) return memo.get(key);
let res = city === finish ? 1 : 0;
for (let j = 0; j < n; j++) {
if (j === city) continue;
const cost = Math.abs(locations[city] - locations[j]);
if (cost <= gas) res = (res + f(j, gas - cost)) % MOD;
}
memo.set(key, res);
return res;
}
return f(start, fuel);
}class Solution {
int MOD = 1_000_000_007;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
int n = locations.length;
Long[][] memo = new Long[n][fuel + 1];
return (int) f(locations, finish, start, fuel, memo);
}
long f(int[] loc, int finish, int city, int gas, Long[][] memo) {
if (memo[city][gas] != null) return memo[city][gas];
long res = city == finish ? 1 : 0;
for (int j = 0; j < loc.length; j++) {
if (j == city) continue;
int cost = Math.abs(loc[city] - loc[j]);
if (cost <= gas) res = (res + f(loc, finish, j, gas - cost, memo)) % MOD;
}
return memo[city][gas] = res;
}
}int MOD = 1e9 + 7;
long f(vector<int>& loc, int finish, int city, int gas, vector<vector<long>>& memo) {
if (memo[city][gas] != -1) return memo[city][gas];
long res = city == finish ? 1 : 0;
for (int j = 0; j < (int)loc.size(); j++) {
if (j == city) continue;
int cost = abs(loc[city] - loc[j]);
if (cost <= gas) res = (res + f(loc, finish, j, gas - cost, memo)) % MOD;
}
return memo[city][gas] = res;
}
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
vector<vector<long>> memo(locations.size(), vector<long>(fuel + 1, -1));
return (int) f(locations, finish, start, fuel, memo);
}Explanation
Think of each "situation" you can be in as a pair: which city you are standing on and how much fuel you have left. That pair is all that matters for the future — how you arrived there is irrelevant. So we define f(city, gas) = the number of valid routes that start at city with gas fuel and finish at the target city.
The key insight is that arriving at finish already counts as one complete route, but you are also allowed to keep driving. So whenever city == finish we seed the answer with 1; otherwise we seed with 0. Then, for every other city j, if the trip cost abs(locations[city] − locations[j]) fits in the remaining fuel, we add f(j, gas − cost) — the number of routes from there onward.
Without memoization this branches into an exponential number of paths, because the same (city, gas) pair gets recomputed over and over. There are only n × (fuel + 1) distinct pairs, so we cache each result the first time we compute it. Every later visit to the same pair is an instant table lookup.
Walking the example locations = [2, 3, 6, 8, 4], start = 1, finish = 3, fuel = 5: city 1 sits at position 3 and city 3 at position 8, a distance of 5, so the direct hop 1→3 uses all the fuel — one route. Detours through city 2 (position 6) and city 4 (position 4) give 1→2→3, 1→4→3, and 1→4→2→3, each also within budget. That is 4 routes total.
Because every answer is summed up many times across long routes, we take everything modulo 109+7 to keep the numbers from overflowing.