Formatted question description: https://leetcode.ca/all/1575.html

# 1575. Count All Possible Routes (Hard)

You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers startfinish 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

Related Topics:
Dynamic Programming

## Solution 1. Top-down DP

Let dp[i][j] be the count of all possible routes from city i with j fuel to city finish.

The initial state is dp[start][fuel].

Assume we can go from city i to city k, dp[i][j] += dp[k][j - dist(i, k)].

When i == finish and j >= 0, we should add 1 to dp[i][j].

dp[i][j] = sum( dp[k][j - dist[i, k]] | j - dist[i, k] >= 0 )
+ (i == start ? 1 : 0)


dp[start][fuel] is the answer.

// OJ: https://leetcode.com/problems/count-all-possible-routes/

// Time: O(N^2 * F)
// Space: O(NF)
class Solution {
long dp[101][201] = {}, mod = 1e9+7, finish;
int dist(vector<int> &A, int a, int b) {
return abs(A[a] - A[b]);
}
int dfs(vector<int> &A, int start, int fuel) {
if (dp[start][fuel]) return dp[start][fuel];
long ans = 0;
if (start == finish) ans++;
for (int i = 0; i < A.size(); ++i) {
if (i == start || dist(A, start, i) + dist(A, i, finish) > fuel) continue;
ans = (ans + dfs(A, i, fuel - dist(A, i, start))) % mod;
}
return dp[start][fuel] = ans;
}
public:
int countRoutes(vector<int>& A, int start, int finish, int fuel) {
this->finish = finish;
return dfs(A, start, fuel);
}
};


## Solution 2.

left[i][f]: the count of routes whose last move is leftwards to location i with f fuel

right[i][f]: the count of routes whose last move is rightwards to location i with f fuel

left[j][f] = left[j+1][f-d(j, j+1)] + right[j+1][f-d(j, j+1)] // go to j + 1 first then j
+ left[j+2][f-d(j, j+2)] + right[j+2][f-d(j, j+2)] // go to j + 2 first then j
+ ...
+ left[j+k][f-d(j, j+k)] + right[j+k][f-d(j, j+2)] // go to j + k first then j


We can apply this equation recursively so that all the left are replaced with right in the right side of the equation.

left[j][f] = right[j+1][f-d(j, j+1)]
+ 2 * right[j+2][f-d(j, j+2)]
+ ...
+ 2^(k-1) * right[j+k][f-d(j, j+k)]


In the righthand-side, the 2nd to last terms can be expressed as 2 * left[j+1][f-d(j, j+1)] because

left[j+1][f] = right[j+2][f-d(j+1, j+2)]
+ 2 * right[j+3][f-d(j+1, j+3)]
+ ...
+ 2^(k-2) * right[j+1+k-1][f-d(j+1, j+1+k-1)]

left[j+1][f-d(j, j+1)] = right[j+2][f-d(j, j+2)]
+ 2 * right[j+3][f-d(j, j+3)]
+ ...
+ 2^(k-2) * right[j+k][f-d(j, j+k)]


So we have this equation

left[j][f] = right[j+1][f-d(j, j+1)] + 2 * left[j+1][f-d(j, j+1)]


Symmetrically, we have

right[j][f] = left[j-1][f-d(j, j-1)] + 2 * right[j-1][f-d(j, j-1)]

// OJ: https://leetcode.com/problems/count-all-possible-routes/

// Time: O(NlogN + NF)
// Space: O(NF)
class Solution {
public:
int countRoutes(vector<int>& A, int start, int finish, int fuel) {
int mod = 1e9+7, s = A[start], f = A[finish];
sort(begin(A), end(A));
start = lower_bound(begin(A), end(A), s) - begin(A);
finish = lower_bound(begin(A), end(A), f) - begin(A);
vector<vector<int>> left(A.size(), vector<int>(fuel + 1));
vector<vector<int>> right(A.size(), vector<int>(fuel + 1));
for (int f = 1; f <= fuel; ++f) {
for (int j = 0; j < A.size() - 1; ++j) {
int d = A[j + 1] - A[j];
if (f > d) left[j][f] = (right[j + 1][f - d] + 2 * left[j + 1][f - d] % mod) % mod;
else if (f == d) left[j][f] = j + 1 == start;
}
for (int j = 1; j < A.size(); ++j) {
int d = A[j] - A[j - 1];
if (f > d) right[j][f] = (left[j - 1][f - d] + 2 * right[j - 1][f - d] % mod) % mod;
else if (f == d) right[j][f] = j - 1 == start;
}
}
int ans = start == finish;
for (int f = 1; f <= fuel; ++f) ans = ((ans + left[finish][f]) % mod + right[finish][f]) % mod;
return ans;
}
};


Java

class Solution {
static final int MODULO = 1000000007;

public int countRoutes(int[] locations, int start, int finish, int fuel) {
int length = locations.length;
long[][] dp = new long[length][fuel + 1];
for (int i = 0; i < length; i++)
Arrays.fill(dp[i], -1);
return (int) dp(dp, locations, start, finish, fuel);
}

public long dp(long[][] dp, int[] locations, int start, int finish, int fuel) {
if (dp[start][fuel] == -1) {
long count = 0;
if (start == finish)
count++;
int length = locations.length;
for (int i = 0; i < length; i++) {
if (i != start) {
int remain = fuel - Math.abs(locations[start] - locations[i]);
if (remain >= 0)
count += dp(dp, locations, i, finish, remain);
}
}
dp[start][fuel] = count % MODULO;
}
return dp[start][fuel];
}
}