Skip to content

1575. Count All Possible Routes 👍

Approach 1: Top-down

  • Time: $O(|\texttt{locations}|^2|\texttt{fuel}|)$
  • Space: $O(|\texttt{locations}||\texttt{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
class Solution {
 public:
  int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
    vector<vector<int>> mem(locations.size(), vector<int>(fuel + 1, -1));
    return countRoutes(locations, start, finish, fuel, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of ways to reach the `finish` city from the i-th city
  // with `fuel` fuel.
  int countRoutes(const vector<int>& locations, int i, int finish, int fuel,
                  vector<vector<int>>& mem) {
    if (fuel < 0)
      return 0;
    if (mem[i][fuel] != -1)
      return mem[i][fuel];

    int res = i == finish ? 1 : 0;
    for (int j = 0; j < locations.size(); ++j) {
      if (j == i)
        continue;
      res += countRoutes(locations, j, finish,
                         fuel - abs(locations[i] - locations[j]), mem);
      res %= kMod;
    }

    return mem[i][fuel] = res;
  }
};

 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
class Solution {
  public int countRoutes(int[] locations, int start, int finish, int fuel) {
    Integer[][] mem = new Integer[locations.length][fuel + 1];
    return countRoutes(locations, start, finish, fuel, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of ways to reach the `finish` city from the i-th city
  // with `fuel` fuel.
  private int countRoutes(int[] locations, int i, int finish, int fuel, Integer[][] mem) {
    if (fuel < 0)
      return 0;
    if (mem[i][fuel] != null)
      return mem[i][fuel];

    int res = (i == finish) ? 1 : 0;
    for (int j = 0; j < locations.length; ++j) {
      if (j == i)
        continue;
      res += countRoutes(locations, j, finish, fuel - Math.abs(locations[i] - locations[j]), mem);
      res %= kMod;
    }

    return mem[i][fuel] = res;
  }
}

 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
class Solution:
  def countRoutes(
      self,
      locations: list[int],
      start: int,
      finish: int,
      fuel: int,
  ) -> int:
    kMod = 1_000_000_007

    @functools.lru_cache(None)
    def dp(i: int, fuel: int) -> int:
      """
      Returns the number of ways to reach the `finish` city from the i-th city
      with `fuel` fuel.
      """
      if fuel < 0:
        return 0

      res = 1 if i == finish else 0
      for j in range(len(locations)):
        if j == i:
          continue
        res += dp(j, fuel - abs(locations[i] - locations[j]))
        res %= kMod

      return res

    return dp(start, fuel)

Approach 2: Bottom-up

  • Time: $O(|\texttt{locations}|^2|\texttt{fuel}|)$
  • Space: $O(|\texttt{locations}||\texttt{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
class Solution {
 public:
  int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
    constexpr int kMod = 1'000'000'007;
    const int n = locations.size();
    // dp[i][j] := the number of ways to reach the `finish` city from the i-th
    // city with `j` fuel
    vector<vector<int>> dp(n, vector<int>(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;
          const int requiredFuel = abs(locations[i] - locations[j]);
          if (requiredFuel <= f) {
            dp[i][f] += dp[j][f - requiredFuel];
            dp[i][f] %= kMod;
          }
        }

    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
class Solution {
  public int countRoutes(int[] locations, int start, int finish, int fuel) {
    final int kMod = 1_000_000_007;
    int n = locations.length;
    // dp[i][j] := the number of ways to reach the `finish` city from the i-th
    // city with `j` fuel
    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;
          final int requiredFuel = Math.abs(locations[i] - locations[j]);
          if (requiredFuel <= f) {
            dp[i][f] += dp[j][f - requiredFuel];
            dp[i][f] %= kMod;
          }
        }

    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
28
class Solution:
  def countRoutes(
      self,
      locations: list[int],
      start: int,
      finish: int,
      fuel: int,
  ) -> int:
    kMod = 1_000_000_007
    n = len(locations)
    # dp[i][j] := the number of ways to reach the `finish` city from the i-th
    # city with `j` fuel
    dp = [[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
          requiredFuel = abs(locations[i] - locations[j])
          if requiredFuel <= f:
            dp[i][f] += dp[j][f - requiredFuel]
            dp[i][f] %= kMod

    return dp[start][fuel]