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) {
    // dp[i][j] := # of ways to reach `finish` from i-th city with j fuel
    dp.resize(locations.size(), vector<int>(fuel + 1, -1));
    vector<vector<int>> dp(locations.size(), vector<int>(fuel + 1, -1));
    return count(locations, start, finish, fuel);
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  vector<vector<int>> dp;

  int count(const vector<int>& locations, int i, int finish, int fuel) {
    if (fuel < 0)
      return 0;
    if (dp[i][fuel] != -1)
      return dp[i][fuel];

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

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

  private static final int kMod = 1_000_000_007;
  private Integer[][] dp;

  private int count(int[] locations, int i, int finish, int fuel) {
    if (fuel < 0)
      return 0;
    if (dp[i][fuel] != null)
      return dp[i][fuel];

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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:
      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)