给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量
每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。
请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。
请你返回从 start 到 finish 所有可能路径的数目。
由于答案可能很大， 请将它对 10^9 + 7 取余后返回。
示例 1：
输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5 输出：4 解释：以下为所有可能路径，每一条都用了 5 单位的汽油： 1 -> 3 1 -> 2 -> 3 1 -> 4 -> 3 1 -> 4 -> 2 -> 3
示例 2：
输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6 输出：5 解释：以下为所有可能的路径： 1 -> 0，使用汽油量为 fuel = 1 1 -> 2 -> 0，使用汽油量为 fuel = 5 1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3 1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
示例 3：
输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3 输出：0 解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。
提示：
2 <= locations.length <= 1001 <= locations[i] <= 109- 所有
locations中的整数 互不相同 。 0 <= start, finish < locations.length1 <= fuel <= 200
方法一：记忆化搜索
class Solution:
def countRoutes(
self, locations: List[int], start: int, finish: int, fuel: int
) -> int:
@cache
def dfs(i, t):
if abs(locations[i] - locations[finish]) > t:
return 0
res = int(i == finish)
for j, v in enumerate(locations):
if j != i:
if (cost := abs(locations[i] - v)) <= t:
res += dfs(j, t - cost)
return res % mod
mod = 10**9 + 7
return dfs(start, fuel)class Solution {
private int[][] f;
private int[] locations;
private int target;
private static final int MOD = (int) 1e9 + 7;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
int n = locations.length;
f = new int[n + 1][fuel + 1];
this.locations = locations;
target = finish;
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], -1);
}
return dfs(start, fuel);
}
private int dfs(int i, int t) {
if (f[i][t] != -1) {
return f[i][t];
}
if (Math.abs(locations[i] - locations[target]) > t) {
return 0;
}
int res = i == target ? 1 : 0;
for (int j = 0; j < locations.length; ++j) {
if (j != i) {
int cost = Math.abs(locations[i] - locations[j]);
if (cost <= t) {
res += dfs(j, t - cost);
res %= MOD;
}
}
}
f[i][t] = res;
return res;
}
}class Solution {
public:
const int mod = 1e9 + 7;
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
int n = locations.size();
vector<vector<int>> f(n + 1, vector<int>(fuel + 1, -1));
return dfs(start, fuel, locations, finish, f);
}
int dfs(int i, int t, vector<int>& locations, int target, vector<vector<int>>& f) {
if (f[i][t] != -1) return f[i][t];
if (abs(locations[i] - locations[target]) > t) return 0;
int res = i == target;
for (int j = 0; j < locations.size(); ++j) {
if (j == i) continue;
int cost = abs(locations[i] - locations[j]);
if (cost <= t) res = (res + dfs(j, t - cost, locations, target, f)) % mod;
}
f[i][t] = res;
return res;
}
};func countRoutes(locations []int, start int, finish int, fuel int) int {
n := len(locations)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, fuel+1)
for j := range f[i] {
f[i][j] = -1
}
}
mod := int(1e9) + 7
var dfs func(int, int) int
dfs = func(i, t int) int {
if f[i][t] != -1 {
return f[i][t]
}
if abs(locations[i]-locations[finish]) > t {
return 0
}
res := 0
if i == finish {
res++
}
for j, v := range locations {
if j != i {
cost := abs(locations[i] - v)
if cost <= t {
res = (res + dfs(j, t-cost)) % mod
}
}
}
f[i][t] = res
return res
}
return dfs(start, fuel)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}