Skip to content

Latest commit

 

History

History
181 lines (168 loc) · 5.99 KB

1575. Count All Possible Routes.md

File metadata and controls

181 lines (168 loc) · 5.99 KB

1575. Count All Possible Routes

the last one in Biweekly Contest 34.

Difficulty : Hard

Related Topics : Dynamic Programming

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.

Example 1:

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:

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:

Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
Output: 0
Explanation: It's impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.

Example 4:

Input: locations = [2,1,5], start = 0, finish = 0, fuel = 3
Output: 2
Explanation: There are two possible routes, 0 and 0 -> 1 -> 0.

Example 5:

Input: locations = [1,2,3], start = 0, finish = 2, fuel = 40
Output: 615088286
Explanation: The total number of possible routes is 2615088300. Taking this number modulo 10^9 + 7 gives us 615088286.

Constraints:

  • 2 <= locations.length <= 100
  • 1 <= locations[i] <= 10^9
  • All integers in locations are distinct.
  • 0 <= start, finish < locations.length
  • 1 <= fuel <= 200

Solution

  • mine
    • Java
      • ``
  • the most votes

  • Recursive & Memorize Runtime: 123 ms, faster than 50.00%, Memory Usage: 39.3 MB, less than 50.00% of Java online submissions

    // O(N^2 * K)time
// O(N * K)space
public int countRoutes(int[] locations, int start, int finish, int fuel) {
    int n = locations.length;
    long[][] dp = new long[n][fuel + 1];
    for (int i = 0; i < n; ++i) {
        Arrays.fill(dp[i], -1);
    }
    return (int) solve(locations, start, finish, dp, fuel);
}

// dp[curCity][fuel] = number of ways to reach finish, when we are at city `curCity` with fuel `fuel`
private long solve(int[] locations, int curCity, int e, long[][] dp, int fuel) {
    // 4. There is no further way left.
    if (fuel < 0) return 0;
    if (dp[curCity][fuel] != -1) return dp[curCity][fuel];
    // 3. Now, if we have atleast 1 way of reaching `end`, add 1 to the answer. But don't stop right here, keep going, there might be more ways :)
    long ans = (curCity == e) ? 1 : 0;
    for (int nextCity = 0; nextCity < locations.length; ++nextCity) {
        // 1. Visit all cities except `curCity`.
        if (nextCity != curCity) {
            // 2. Continue this process recursively.
            ans = (ans + solve(locations, nextCity, e, dp, fuel - Math.abs(locations[curCity] - locations[nextCity]))) % 1000000007;
        }
    }
    return dp[curCity][fuel] = ans;
}

  • DFS & Memorize Runtime: 237 ms, faster than 19.77%,Memory Usage: 44.4 MB, less than 14.85% of Java online submissions

    long MOD = 1000000007;
Map<Long, Long> mem = new HashMap<>();
public int countRoutes(int[] locations, int start, int finish, int fuel) {
    return (int) (dfs(locations, start, finish, fuel) % MOD);
}
public long dfs(int[] l, int s, int f, int fuel) {
    long key = s * 1000000 + f * 1000  + fuel;
    if (mem.containsKey(key)) return mem.get(key);
    long cnt = 0;
    if (s == f) cnt++;
    for (int j = 0; j < l.length; j++) {
        int left = fuel - Math.abs(l[j] - l[s]);
        if (j != s && left >= 0) {
            cnt += dfs(l, j, f, left);
        }
    }
    cnt %= MOD;
    mem.put(key, cnt);
    return cnt;
}

  • DP Runtime: 442 ms, faster than 50.00%, Memory Usage: 39.2 MB, less than 50.00% of Java online submissions

    // O(N^2 * K)time
// O(N * K)space

//dp[i][j] is the count we go to location i use j fuel.
//the res = dp[finish][0] + dp[finish][1] + .. + dp[finish][fuel]
long[][] dp = new long[101][201];
long mod = 1_000_000_007;
public int countRoutes(int[] loc, int start, int finish, int fuel) {
    int n = loc.length;
    dp[start][0] = 1;
    for (int k = 0; k < fuel; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
                int dis = Math.abs(loc[i] - loc[j]);
                if (k + dis > 200) continue;
                dp[j][k + dis] += dp[i][k];
                dp[j][k + dis] %= mod;
            }
        }
    }
    long res = 0;
    for (int k = 0; k <= fuel; k++) {
        res += dp[finish][k];
        res %= mod;
    }
    return (int) res;
}