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 10^9 + 7.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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:

1
2
3
4
5

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.

Solution

Method 1 – Dynamic Programming with Memoization

Intuition

The problem asks for the number of possible routes from start to finish using at most fuel units, possibly revisiting cities. Since each move reduces fuel and cities can be revisited, the problem has overlapping subproblems and optimal substructure, making it suitable for DP with memoization. At each city with a given fuel, the answer depends only on the current city and remaining fuel.

Approach

  1. Define a recursive function dfs(i, f) that returns the number of ways to reach finish from city i with f fuel left.
  2. If f < 0, return 0 (not enough fuel).
  3. If at city i with f fuel, initialize ans as 1 if i == finish (can stay at finish).
  4. For each other city j, if moving from i to j costs cost = abs(locations[i] - locations[j]) and f >= cost, recursively call dfs(j, f - cost) and add to ans.
  5. Use memoization to cache results for (i, f) to avoid recomputation.
  6. Return ans % MOD (where MOD = 1e9+7).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
  int countRoutes(vector<int>& loc, int start, int finish, int fuel) {
    int n = loc.size(), MOD = 1e9+7;
    vector<vector<int>> dp(n, vector<int>(fuel+1, -1));
    function<int(int,int)> dfs = [&](int i, int f) {
      if (f < 0) return 0;
      if (dp[i][f] != -1) return dp[i][f];
      int ans = (i == finish) ? 1 : 0;
      for (int j = 0; j < n; ++j) {
        if (j == i) continue;
        int cost = abs(loc[i] - loc[j]);
        if (f >= cost)
          ans = (ans + dfs(j, f - cost)) % MOD;
      }
      return dp[i][f] = ans;
    };
    return dfs(start, fuel);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func countRoutes(loc []int, start int, finish int, fuel int) int {
  n, MOD := len(loc), int(1e9+7)
  dp := make([][]int, n)
  for i := range dp {
    dp[i] = make([]int, fuel+1)
    for j := range dp[i] {
      dp[i][j] = -1
    }
  }
  var dfs func(i, f int) int
  dfs = func(i, f int) int {
    if f < 0 {
      return 0
    }
    if dp[i][f] != -1 {
      return dp[i][f]
    }
    ans := 0
    if i == finish {
      ans = 1
    }
    for j := 0; j < n; j++ {
      if j == i {
        continue
      }
      cost := loc[i] - loc[j]
      if cost < 0 {
        cost = -cost
      }
      if f >= cost {
        ans = (ans + dfs(j, f-cost)) % MOD
      }
    }
    dp[i][f] = ans
    return ans
  }
  return dfs(start, fuel)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
  static final int MOD = 1_000_000_007;
  public int countRoutes(int[] loc, int start, int finish, int fuel) {
    int n = loc.length;
    Integer[][] dp = new Integer[n][fuel+1];
    return dfs(loc, start, finish, fuel, dp);
  }
  int dfs(int[] loc, int i, int finish, int f, Integer[][] dp) {
    if (f < 0) return 0;
    if (dp[i][f] != null) return dp[i][f];
    int ans = (i == finish) ? 1 : 0;
    for (int j = 0; j < loc.length; ++j) {
      if (j == i) continue;
      int cost = Math.abs(loc[i] - loc[j]);
      if (f >= cost)
        ans = (ans + dfs(loc, j, finish, f - cost, dp)) % MOD;
    }
    return dp[i][f] = ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
  private val MOD = 1_000_000_007
  fun countRoutes(loc: IntArray, start: Int, finish: Int, fuel: Int): Int {
    val n = loc.size
    val dp = Array(n) { IntArray(fuel + 1) { -1 } }
    fun dfs(i: Int, f: Int): Int {
      if (f < 0) return 0
      if (dp[i][f] != -1) return dp[i][f]
      var ans = if (i == finish) 1 else 0
      for (j in 0 until n) {
        if (j == i) continue
        val cost = kotlin.math.abs(loc[i] - loc[j])
        if (f >= cost)
          ans = (ans + dfs(j, f - cost)) % MOD
      }
      dp[i][f] = ans
      return ans
    }
    return dfs(start, fuel)
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
  def countRoutes(self, loc: list[int], start: int, finish: int, fuel: int) -> int:
    MOD = 10**9 + 7
    n = len(loc)
    from functools import cache

    @cache
    def dfs(i: int, f: int) -> int:
      if f < 0:
        return 0
      ans = 1 if i == finish else 0
      for j in range(n):
        if j == i:
          continue
        cost = abs(loc[i] - loc[j])
        if f >= cost:
          ans = (ans + dfs(j, f - cost)) % MOD
      return ans

    return dfs(start, fuel)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
  pub fn count_routes(loc: Vec<i32>, start: i32, finish: i32, fuel: i32) -> i32 {
    const MOD: i32 = 1_000_000_007;
    let n = loc.len();
    let mut dp = vec![vec![-1; (fuel+1) as usize]; n];
    fn dfs(i: usize, f: i32, finish: usize, loc: &Vec<i32>, dp: &mut Vec<Vec<i32>>) -> i32 {
      if f < 0 { return 0; }
      if dp[i][f as usize] != -1 { return dp[i][f as usize]; }
      let mut ans = if i == finish { 1 } else { 0 };
      for j in 0..loc.len() {
        if j == i { continue; }
        let cost = (loc[i] - loc[j]).abs();
        if f >= cost {
          ans = (ans + dfs(j, f - cost, finish, loc, dp)) % MOD;
        }
      }
      dp[i][f as usize] = ans;
      ans
    }
    dfs(start as usize, fuel, finish as usize, &loc, &mut dp)
  }
}

Complexity

  • ⏰ Time complexity: O(n * fuel^2) (There are n cities and fuel+1 fuel states; for each state, we may check up to n neighbors.)
  • 🧺 Space complexity: O(n * fuel) (For memoization table.)

Method 2 – Bottom-Up Dynamic Programming

Intuition

Instead of solving subproblems recursively, we can build up the solution iteratively using a DP table. For each city and each possible fuel amount, we compute the number of ways to reach the finish city. This avoids recursion and stack overhead, and makes the state transitions explicit.

Approach

  1. Let dp[i][f] be the number of ways to reach the finish city from city i with f fuel left.
  2. Initialize dp[i][0..fuel] to 0 for all i.
  3. For all f from 0 to fuel, set dp[finish][f] = 1 (since being at finish with any fuel is a valid route).
  4. For each f from 0 to fuel, for each city i, for each city j != i:
  • If cost = abs(loc[i] - loc[j]) and f >= cost, add dp[j][f - cost] to dp[i][f].
  1. The answer is dp[start][fuel].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
  int countRoutes(vector<int>& loc, int start, int finish, int fuel) {
   int n = loc.size(), MOD = 1e9+7;
   vector<vector<int>> dp(n, vector<int>(fuel+1, 0));
   for (int f = 0; f <= fuel; ++f)
    dp[finish][f] = 1;
   for (int f = 0; f <= fuel; ++f) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
       if (i == j) continue;
       int cost = abs(loc[i] - loc[j]);
       if (f >= cost)
        dp[i][f] = (dp[i][f] + dp[j][f - cost]) % MOD;
      }
    }
   }
   return dp[start][fuel];
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func countRoutes(loc []int, start int, finish int, fuel int) int {
  n, MOD := len(loc), int(1e9+7)
  dp := make([][]int, n)
  for i := range dp {
   dp[i] = make([]int, fuel+1)
  }
  for f := 0; f <= fuel; f++ {
   dp[finish][f] = 1
  }
  for f := 0; f <= fuel; f++ {
   for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
      if i == j {
       continue
      }
      cost := loc[i] - loc[j]
      if cost < 0 {
       cost = -cost
      }
      if f >= cost {
       dp[i][f] = (dp[i][f] + dp[j][f-cost]) % MOD
      }
    }
   }
  }
  return dp[start][fuel]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
  static final int MOD = 1_000_000_007;
  public int countRoutes(int[] loc, int start, int finish, int fuel) {
   int n = loc.length;
   int[][] dp = new int[n][fuel+1];
   for (int f = 0; f <= fuel; ++f)
    dp[finish][f] = 1;
   for (int f = 0; 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(loc[i] - loc[j]);
       if (f >= cost)
        dp[i][f] = (dp[i][f] + dp[j][f - cost]) % MOD;
      }
    }
   }
   return dp[start][fuel];
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
  private val MOD = 1_000_000_007
  fun countRoutes(loc: IntArray, start: Int, finish: Int, fuel: Int): Int {
   val n = loc.size
   val dp = Array(n) { IntArray(fuel + 1) }
   for (f in 0..fuel) dp[finish][f] = 1
   for (f in 0..fuel) {
    for (i in 0 until n) {
      for (j in 0 until n) {
       if (i == j) continue
       val cost = kotlin.math.abs(loc[i] - loc[j])
       if (f >= cost)
        dp[i][f] = (dp[i][f] + dp[j][f - cost]) % MOD
      }
    }
   }
   return dp[start][fuel]
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
  def countRoutes(self, loc: list[int], start: int, finish: int, fuel: int) -> int:
   MOD = 10**9 + 7
   n = len(loc)
   dp: list[list[int]] = [[0] * (fuel + 1) for _ in range(n)]
   for f in range(fuel + 1):
    dp[finish][f] = 1
   for f in range(fuel + 1):
    for i in range(n):
      for j in range(n):
       if i == j:
        continue
       cost = abs(loc[i] - loc[j])
       if f >= cost:
        dp[i][f] = (dp[i][f] + dp[j][f - cost]) % MOD
   return dp[start][fuel]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
  pub fn count_routes(loc: Vec<i32>, start: i32, finish: i32, fuel: i32) -> i32 {
   const MOD: i32 = 1_000_000_007;
   let n = loc.len();
   let mut dp = vec![vec![0; (fuel+1) as usize]; n];
   for f in 0..=fuel as usize {
    dp[finish as usize][f] = 1;
   }
   for f in 0..=fuel as usize {
    for i in 0..n {
      for j in 0..n {
       if i == j { continue; }
       let cost = (loc[i] - loc[j]).abs() as usize;
       if f >= cost {
        dp[i][f] = (dp[i][f] + dp[j][f - cost]) % MOD;
       }
      }
    }
   }
   dp[start as usize][fuel as usize]
  }
}

Complexity

  • ⏰ Time complexity: O(n^2 * fuel). (For each of fuel+1 fuel states, for each of n cities, we check all n possible moves.)
  • 🧺 Space complexity: O(n * fuel). (DP table of size n x (fuel+1).)