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: DP
dp[j][f] := # of ways to start from city ‘start’ to reach city ‘j’ with fuel level f.
dp[j][f] = sum(dp[i][f + d]) d = dist(i, j)
init: dp[start][fuel] = 1
Time complexity: O(n^2*fuel)
Space complexity: O(n*fuel)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int countRoutes(vector<int>& x, int start, int finish, int fuel) { constexpr int kMod = 1e9 + 7; const int n = x.size(); vector<vector<int>> dp(n, vector<int>(fuel + 1)); dp[start][fuel] = 1; for (int f = fuel; f > 0; --f) for (int i = 0; i < n; ++i) { if (!dp[i][f] || abs(x[i] - x[finish]) > f) continue; // pruning. for (int j = 0; j < n; ++j) { const int d = abs(x[i] - x[j]); if (i == j || f < d) continue; dp[j][f - d] = (dp[j][f - d] + dp[i][f]) % kMod; } } return accumulate(begin(dp[finish]), end(dp[finish]), 0LL) % kMod; } }; |
Python3
1 2 3 4 5 6 7 8 9 |
# Author: Huahua class Solution: def countRoutes(self, x: List[int], start: int, finish: int, fuel: int) -> int: @lru_cache(None) def dp(i, f): # ways to reach |finsh| from |i| with |f| fuel. if f < 0: return 0 return (sum(dp(j, f - abs(x[i] - x[j])) for j in range(len(x)) if i != j) + (i == finish)) % (10**9 + 7) return dp(start, fuel) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment