Count All Possible Routes: DP on City and Fuel

You are given an array of city locations, a start city, a finish city, and a fuel budget. Moving between cities costs fuel equal to the absolute difference in their locations. You may revisit cities, including the start and finish. How many distinct routes go from start to finish without exceeding the fuel budget?

This is LeetCode 1575: Count All Possible Routes, a hard DP problem that tests whether you can define a clean two-dimensional state and handle the subtlety that arriving at the finish does not end the journey. You can keep going, pass through the finish again, and each arrival counts separately.

The problem

Given locations (an integer array), start, finish, and fuel:

• Moving from city i to city j costs |locations[i] - locations[j]| fuel.
• You can visit any city (including start and finish) any number of times.
• Return the count of all possible routes from start to finish, modulo 10^9 + 7.

For example, with locations = [2, 3, 6, 8, 4], start = 1, finish = 3, and fuel = 5, the answer is 4. The four routes are:

1. 1 -> 3 (cost 5)
2. 1 -> 2 -> 3 (cost 3 + 2 = 5)
3. 1 -> 4 -> 3 (cost 1 + 4 = 5)
4. 1 -> 4 -> 2 -> 3 (cost 1 + 2 + 2 = 5)

The brute force approach

The recursive idea is natural. From any city with some remaining fuel, try moving to every other city. If you have enough fuel for the trip, recurse from the new city with reduced fuel. Every time you are standing at the finish city, that counts as one valid route, but you do not stop there. You keep exploring.

def count_routes_brute(locations, start, finish, fuel):
    MOD = 10**9 + 7
    n = len(locations)

    def dfs(city, remaining):
        count = 1 if city == finish else 0
        for j in range(n):
            if j != city:
                cost = abs(locations[city] - locations[j])
                if cost <= remaining:
                    count = (count + dfs(j, remaining - cost)) % MOD
        return count

    return dfs(start, fuel)

This explores every possible path, which can be exponential. The recursion branches up to n - 1 ways at each step and the depth can be as large as the fuel budget. It will time out on any nontrivial input.

The key insight

The brute force recomputes the same subproblems many times. The state of the recursion is fully described by two values: which city you are in, and how much fuel you have left. If you have already computed how many routes exist from city c with f fuel remaining, you can reuse that result.

This gives you an n x (fuel + 1) table. Each cell does O(n) work (trying all other cities). Total time: O(n^2 * fuel). That is efficient enough for the constraints (n up to 100, fuel up to 200).

Step-by-step walkthrough

Let's trace the DP table for locations = [2, 3, 6, 8, 4], start = 1, finish = 3, fuel = 5. Each cell dp(city, f) stores how many routes lead from that city to city 3 using at most f fuel.

The table fills from fuel = 0 upward. At each fuel level, every city checks which other cities it can afford to visit, and sums up the route counts from those destinations at the reduced fuel level.

The code

def count_routes(locations, start, finish, fuel):
    MOD = 10**9 + 7
    n = len(locations)
    memo = {}

    def dp(city, remaining):
        if remaining < 0:
            return 0
        if (city, remaining) in memo:
            return memo[(city, remaining)]

        result = 1 if city == finish else 0

        for j in range(n):
            if j != city:
                cost = abs(locations[city] - locations[j])
                if cost <= remaining:
                    result = (result + dp(j, remaining - cost)) % MOD

        memo[(city, remaining)] = result
        return result

    return dp(start, fuel)

The top-down approach with memoization is the most natural way to write this. The memo dictionary caches each (city, fuel) pair so no state is computed twice.

You can also write it bottom-up by iterating fuel from 0 to the maximum and filling an n-length array at each level:

def count_routes(locations, start, finish, fuel):
    MOD = 10**9 + 7
    n = len(locations)
    dp = [[0] * n for _ in range(fuel + 1)]

    for f in range(fuel + 1):
        dp[f][finish] = 1

    for f in range(1, fuel + 1):
        for city in range(n):
            for j in range(n):
                if j != city:
                    cost = abs(locations[city] - locations[j])
                    if cost <= f:
                        dp[f][city] = (dp[f][city] + dp[f - cost][j]) % MOD

    return dp[fuel][start]

Complexity analysis

Where n is the number of cities and fuel is the initial fuel budget.

Both DP approaches have the same asymptotic complexity. The top-down version only computes reachable states (which can be fewer), while the bottom-up version fills the entire table. For the given constraints (n up to 100, fuel up to 200), both are fast enough.

The building blocks

1. Two-dimensional DP state

The state here is (city, fuel_remaining). Many DP problems have a single dimension (like amount in Coin Change). This problem requires two because you need to know both where you are and how much fuel you have. The same two-dimensional pattern appears in problems like Interleaving String, Edit Distance, and any grid-based DP.

2. Counting paths with revisits

Unlike shortest-path problems where you want to avoid cycles, this problem explicitly allows revisiting cities. The fuel budget is what prevents infinite loops. Every unit of fuel spent is gone forever, so the recursion is guaranteed to terminate. This is the same structural guarantee that makes Coin Change terminate: each recursive call reduces a finite resource.

3. Modular arithmetic throughout

Because the answer can be astronomically large, every addition is taken modulo 10^9 + 7. This is a standard pattern in counting problems. The key rule: apply the modulo after every addition, not just at the end.

Edge cases

• Start equals finish: the answer is at least 1 (you are already there). You may also leave and return if fuel allows.
• Fuel is 0: the answer is 1 if start == finish, otherwise 0.
• Only two cities: the problem reduces to counting how many times you can bounce back and forth between them with the given fuel.
• All cities at the same location: every move costs 0 fuel, so there are infinitely many routes. However, the constraints guarantee locations are distinct, so this case does not arise.
• Fuel is exactly enough for one direct trip: only the direct route counts (plus any routes through intermediate cities that happen to sum to the same cost).

From understanding to recall

You have walked through the DP table and the logic makes sense. But can you write the recurrence from scratch next week? In an interview, will you remember that the finish city contributes 1 at every fuel level, not just fuel = 0?

These details are easy to forget under pressure. Spaced repetition locks them in. You write the dp(city, fuel) definition from memory, trace through a small example, and after a few reps the two-dimensional state and the "finish always counts" subtlety become automatic.

The two-dimensional DP with counting pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Coin Change - The classic 1D DP counting/optimization problem, same "try all choices and combine results" structure with a simpler state
• Unique Paths - A 2D DP problem that counts paths on a grid, building the same intuition for multi-dimensional state spaces
• Climbing Stairs - The gentlest intro to DP, same recursive-to-memoized pipeline with a single dimension