---
comments: true
difficulty: 困难
edit_url: https://github.com/doocs/leetcode/edit/main/solution/1500-1599/1575.Count%20All%20Possible%20Routes/README.md
rating: 2055
source: 第 34 场双周赛 Q4
tags:
- 记忆化搜索
- 数组
- 动态规划
---
# [1575. 统计所有可行路径](https://leetcode.cn/problems/count-all-possible-routes)
[English Version](/solution/1500-1599/1575.Count%20All%20Possible%20Routes/README_EN.md)
## 题目描述
给你一个 互不相同 的整数数组，其中 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
## 解法
### 方法一：记忆化搜索
我们设计一个函数 $dfs(i, k)$，表示从城市 $i$ 出发，剩余汽油量为 $k$ 时，到达目的地 $finish$ 的路径数。那么答案就是 $dfs(start, fuel)$。
函数 $dfs(i, k)$ 的计算过程如下：
- 如果 $k \lt |locations[i] - locations[finish]|$，那么返回 $0$。
- 如果 $i = finish$，那么答案路径数初始时为 $1$，否则为 $0$。
- 然后，我们遍历所有城市 $j$，如果 $j \ne i$，那么我们可以从城市 $i$ 移动到城市 $j$，此时剩余汽油量为 $k - |locations[i] - locations[j]|$，那么我们可以将答案路径数加上 $dfs(j, k - |locations[i] - locations[j]|)$。
- 最后，我们返回答案路径数。
为了避免重复计算，我们可以使用记忆化搜索。
时间复杂度 $O(n^2 \times m)$，空间复杂度 $O(n \times m)$。其中 $n$ 和 $m$ 分别是数组 $locations$ 和 $fuel$ 的大小。
#### Python3
```python
class Solution:
def countRoutes(
self, locations: List[int], start: int, finish: int, fuel: int
) -> int:
@cache
def dfs(i: int, k: int) -> int:
if k < abs(locations[i] - locations[finish]):
return 0
ans = int(i == finish)
for j, x in enumerate(locations):
if j != i:
ans = (ans + dfs(j, k - abs(locations[i] - x))) % mod
return ans
mod = 10**9 + 7
return dfs(start, fuel)
```
#### Java
```java
class Solution {
private int[] locations;
private int finish;
private int n;
private Integer[][] f;
private final int mod = (int) 1e9 + 7;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
n = locations.length;
this.locations = locations;
this.finish = finish;
f = new Integer[n][fuel + 1];
return dfs(start, fuel);
}
private int dfs(int i, int k) {
if (k < Math.abs(locations[i] - locations[finish])) {
return 0;
}
if (f[i][k] != null) {
return f[i][k];
}
int ans = i == finish ? 1 : 0;
for (int j = 0; j < n; ++j) {
if (j != i) {
ans = (ans + dfs(j, k - Math.abs(locations[i] - locations[j]))) % mod;
}
}
return f[i][k] = ans;
}
}
```
#### C++
```cpp
class Solution {
public:
int countRoutes(vector& locations, int start, int finish, int fuel) {
int n = locations.size();
int f[n][fuel + 1];
memset(f, -1, sizeof(f));
const int mod = 1e9 + 7;
function dfs = [&](int i, int k) -> int {
if (k < abs(locations[i] - locations[finish])) {
return 0;
}
if (f[i][k] != -1) {
return f[i][k];
}
int ans = i == finish;
for (int j = 0; j < n; ++j) {
if (j != i) {
ans = (ans + dfs(j, k - abs(locations[i] - locations[j]))) % mod;
}
}
return f[i][k] = ans;
};
return dfs(start, fuel);
}
};
```
#### Go
```go
func countRoutes(locations []int, start int, finish int, fuel int) int {
n := len(locations)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, fuel+1)
for j := range f[i] {
f[i][j] = -1
}
}
const mod = 1e9 + 7
var dfs func(int, int) int
dfs = func(i, k int) (ans int) {
if k < abs(locations[i]-locations[finish]) {
return 0
}
if f[i][k] != -1 {
return f[i][k]
}
if i == finish {
ans = 1
}
for j, x := range locations {
if j != i {
ans = (ans + dfs(j, k-abs(locations[i]-x))) % mod
}
}
f[i][k] = ans
return
}
return dfs(start, fuel)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
```
#### TypeScript
```ts
function countRoutes(locations: number[], start: number, finish: number, fuel: number): number {
const n = locations.length;
const f = Array.from({ length: n }, () => Array(fuel + 1).fill(-1));
const mod = 1e9 + 7;
const dfs = (i: number, k: number): number => {
if (k < Math.abs(locations[i] - locations[finish])) {
return 0;
}
if (f[i][k] !== -1) {
return f[i][k];
}
let ans = i === finish ? 1 : 0;
for (let j = 0; j < n; ++j) {
if (j !== i) {
const x = Math.abs(locations[i] - locations[j]);
ans = (ans + dfs(j, k - x)) % mod;
}
}
return (f[i][k] = ans);
};
return dfs(start, fuel);
}
```
### 方法二：动态规划
我们也可以将方法一的记忆化搜索转换为动态规划。
我们定义 $f[i][k]$ 表示从城市 $i$ 出发，剩余汽油量为 $k$ 时，到达目的地 $finish$ 的路径数。那么答案就是 $f[start][fuel]$。初始时 $f[finish][k]=1$，其余均为 $0$。
接下来，我们从小到大枚举剩余汽油量 $k$，然后枚举所有的城市 $i$，对于每个城市 $i$，我们枚举所有的城市 $j$，如果 $j \ne i$，并且 $|locations[i] - locations[j]| \le k$，那么我们可以从城市 $i$ 移动到城市 $j$，此时剩余汽油量为 $k - |locations[i] - locations[j]|$，那么我们可以将答案路径数加上 $f[j][k - |locations[i] - locations[j]|]$。
最后，我们返回答案路径数 $f[start][fuel]$ 即可。
时间复杂度 $O(n^2 \times m)$，空间复杂度 $O(n \times m)$。其中 $n$ 和 $m$ 分别是数组 $locations$ 和 $fuel$ 的大小。
#### Python3
```python
class Solution:
def countRoutes(
self, locations: List[int], start: int, finish: int, fuel: int
) -> int:
mod = 10**9 + 7
n = len(locations)
f = [[0] * (fuel + 1) for _ in range(n)]
for k in range(fuel + 1):
f[finish][k] = 1
for k in range(fuel + 1):
for i in range(n):
for j in range(n):
if j != i and abs(locations[i] - locations[j]) <= k:
f[i][k] = (
f[i][k] + f[j][k - abs(locations[i] - locations[j])]
) % mod
return f[start][fuel]
```
#### Java
```java
class Solution {
public int countRoutes(int[] locations, int start, int finish, int fuel) {
final int mod = (int) 1e9 + 7;
int n = locations.length;
int[][] f = new int[n][fuel + 1];
for (int k = 0; k <= fuel; ++k) {
f[finish][k] = 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 && Math.abs(locations[i] - locations[j]) <= k) {
f[i][k] = (f[i][k] + f[j][k - Math.abs(locations[i] - locations[j])]) % mod;
}
}
}
}
return f[start][fuel];
}
}
```
#### C++
```cpp
class Solution {
public:
int countRoutes(vector& locations, int start, int finish, int fuel) {
const int mod = 1e9 + 7;
int n = locations.size();
int f[n][fuel + 1];
memset(f, 0, sizeof(f));
for (int k = 0; k <= fuel; ++k) {
f[finish][k] = 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 && abs(locations[i] - locations[j]) <= k) {
f[i][k] = (f[i][k] + f[j][k - abs(locations[i] - locations[j])]) % mod;
}
}
}
}
return f[start][fuel];
}
};
```
#### Go
```go
func countRoutes(locations []int, start int, finish int, fuel int) int {
n := len(locations)
const mod = 1e9 + 7
f := make([][]int, n)
for i := range f {
f[i] = make([]int, fuel+1)
}
for k := 0; k <= fuel; k++ {
f[finish][k] = 1
}
for k := 0; k <= fuel; k++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if j != i && abs(locations[i]-locations[j]) <= k {
f[i][k] = (f[i][k] + f[j][k-abs(locations[i]-locations[j])]) % mod
}
}
}
}
return f[start][fuel]
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
```
#### TypeScript
```ts
function countRoutes(locations: number[], start: number, finish: number, fuel: number): number {
const n = locations.length;
const f = Array.from({ length: n }, () => Array(fuel + 1).fill(0));
for (let k = 0; k <= fuel; ++k) {
f[finish][k] = 1;
}
const mod = 1e9 + 7;
for (let k = 0; k <= fuel; ++k) {
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (j !== i && Math.abs(locations[i] - locations[j]) <= k) {
f[i][k] = (f[i][k] + f[j][k - Math.abs(locations[i] - locations[j])]) % mod;
}
}
}
}
return f[start][fuel];
}
```