#1575

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count All Possible Routes

This problem requires counting all possible routes between cities using fuel efficiently with state transition dynamic programming.

array dynamic programming memoization

Problem Statement

Given an array of distinct positive integers locations, where locations[i] represents city i's position, calculate the total number of routes from a starting city to a finishing city using a limited amount of fuel. You may move between any two cities as long as you have enough fuel, with fuel cost equal to the absolute distance between cities.

You must count every possible route, including revisiting the same city multiple times, as long as fuel remains non-negative. The task is to determine how many distinct sequences of moves allow reaching the finish city from the start city under these constraints.

Examples

Example 1

Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5

Output: 4

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

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

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

Solution Approach

Define State and Transition

Represent each state as (current city index, remaining fuel). For every valid move to another city j, decrease fuel by the distance and recursively compute routes from the new state, summing all possible paths.

Use Memoization

Store results of each state in a DP table keyed by city and fuel remaining. This prevents repeated computations and ensures efficient exploration of all route combinations, which is essential for the exponential branching of moves.

Combine Routes Carefully

Add 1 to the count whenever the finish city is reached in a valid state. Continue exploring other possible moves, aggregating counts while respecting remaining fuel, ensuring revisits do not produce negative fuel.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the number of unique states, bounded by number of cities times fuel capacity. Memoization reduces exponential recursion to O(n * fuel) states, each potentially checking O(n) transitions.

What Interviewers Usually Probe

Focus on memoizing (city, fuel) states rather than tracking exact paths.
Recognize revisiting cities is allowed and must be handled without double-counting errors.
Check edge cases where fuel is insufficient for even the direct move from start to finish.

Common Pitfalls or Variants

Common pitfalls

Failing to memoize states, causing exponential timeouts.
Subtracting fuel incorrectly or allowing negative fuel states.
Ignoring that visiting the same city multiple times is valid and needed for some routes.

Follow-up variants

Compute routes with a maximum number of stops instead of fuel limit.
Count only routes that visit each city at most once while respecting fuel constraints.
Optimize for minimal total fuel to reach finish while counting only feasible paths.

FAQ

What is the main pattern used in Count All Possible Routes?

This problem uses state transition dynamic programming, with states defined by current city and remaining fuel, and transitions representing moving to other cities.

Can I visit the same city multiple times?

Yes, revisiting cities is allowed as long as fuel remains non-negative, which is critical for counting all possible routes correctly.

How do I avoid recalculating the same state?

Use memoization by storing the number of routes for each (city, remaining fuel) state, which reduces redundant computation.

What happens if fuel is insufficient for a direct move?

Such moves are invalid and should not be counted; only transitions where remaining fuel stays non-negative are considered.

Is dynamic programming necessary for this problem?

Yes, without DP the exponential number of possible routes leads to timeouts; DP ensures efficient state exploration and correct counting.

terminal

Solution

Solution 1: Memoization

We design a function $dfs(i, k)$, which represents the number of paths from city $i$ with $k$ remaining fuel to the destination $finish$. So the answer is $dfs(start, fuel)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

Solution 2: Dynamic Programming

We can also convert the memoization of solution 1 into dynamic programming.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

Continue Practicing

#1569 number of ways to reorder array to get same bst #1444 number of ways of cutting a pizza #1728 cat and mouse ii