---

1575. 统计所有可行路径

• 标签：记忆化搜索、数组、动态规划
• 难度：困难

题目链接

• 1575. 统计所有可行路径 - 力扣

题目大意

描述：给定 $n$ 个城市，每个城市有对应的燃油量 $locations[i]$。有一辆车从城市 $start$ 出发，初始油量为 $fuel$，目标城市为 $finish$。

每从城市 $i$ 到城市 $j$ 需要消耗 $|locations[i] - locations[j]|$ 单位油量。可以在任意城市停留或折返。

要求：返回从 $start$ 到 $finish$ 的所有可行路径数量（可经过同一城市多次）。结果对 $10^9 + 7$ 取模。

说明：

• $2 \le n \le 100$。
• $1 \le locations[i] \le 10^9$。
• $0 \le start, finish < n$。
• $1 \le fuel \le 200$。

示例：

• 示例 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

解题思路

思路 1：动态规划（记忆化搜索）

1. 核心思想

阶段是剩余油量 $f$，状态是当前所在城市 $u$。定义 $dp[u][f]$ 表示从城市 $u$ 出发、剩余油量为 $f$ 时，到达 $finish$ 的路径数。

状态转移：从 $u$ 可以移动到任意其他城市 $v$（$v \neq u$），如果油量足够：

$$dp[u][f] = \sum_{v \neq u, cost \le f} dp[v][f - cost]$$

其中 $cost = |locations[u] - locations[v]|$。

边界条件：$dp[finish][\text{任意油量}]$ 初始为 $1$（到达终点后停止也是一种方案，但注意还可以继续走）。

实际上，在 $finish$ 城市时也算一条路径（已经到达），因此 $dp[finish][f]$ 的基础值为 $1$。

2. 具体步骤（自顶向下记忆化搜索）

第 1 步：定义 $memo[u][f]$ 为从 $u$ 出发剩余 $f$ 油量到达 $finish$ 的路径数。

第 2 步：递归函数 $dfs(u, f)$：

• 如果 $memo[u][f]$ 已计算，直接返回。
• 初始化 $res = 0$。
• 如果 $u == finish$，$res = 1$（到达目标，这是一条有效路径）。
• 遍历所有 $v \neq u$：
  • $cost = |locations[u] - locations[v]|$。
  • 若 $cost \le f$，$res = (res + dfs(v, f - cost)) \% MOD$。
• 存入 $memo[u][f]$，返回。

第 3 步：返回 $dfs(start, fuel)$。

3. 具体步骤（自底向上 DP）

第 1 步：定义 $dp[u][f]$ 同上。

第 2 步：初始化 $dp[finish][f] = 1$ 对于所有 $f \in [0, fuel]$。

第 3 步：枚举油量 $f$ 从 $0$ 到 $fuel$，城市 $u$ 从 $0$ 到 $n-1$：

• 若 $dp[u][f] > 0$，枚举所有 $v \neq u$：
  • $cost = |locations[u] - locations[v]|$。
  • 若 $f + cost \le fuel$，$dp[v][f + cost] = (dp[v][f + cost] + dp[u][f]) \% MOD$。

第 4 步：返回 $dp[start][fuel]$。

注意自底向上时，$dp[u][f]$ 表示剩余 $f$ 油量时从 $start$ 到 $u$ 的路径数。这种定义下转移方向不同。

4. 举例说明

以 $locations = [2,3,6,8,4], start = 1, finish = 0, fuel = 5$ 为例：

城市燃油量：$loc[0]=2, loc[1]=3, loc[2]=6, loc[3]=8, loc[4]=4$。

从城市 $1$ 出发，油量 $5$：

• 直接到 $0$：$|3-2|=1 \le 5$，可行。
• $1 \to 4 \to 0$：$|3-4|=1$，$|4-2|=2$，总 $3 \le 5$，可行。
• $1 \to 4 \to 1 \to 0$：油量开销 $1+1+1=3 \le 5$，可行。

最终有 $4$ 条路径。

5. 时间复杂度优化

$fuel \le 200$，$n \le 100$，状态数 $n \times fuel \le 20000$，每个状态转移 $O(n)$，总 $O(n^2 \times fuel) \le 2 \times 10^6$，完全可行。

思路 1：代码

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        MOD = 10 ** 9 + 7
        n = len(locations)
        memo = [[-1] * (fuel + 1) for _ in range(n)]

        def dfs(u: int, f: int) -> int:
            if memo[u][f] != -1:
                return memo[u][f]
            res = 1 if u == finish else 0
            for v in range(n):
                if v == u:
                    continue
                cost = abs(locations[u] - locations[v])
                if cost <= f:
                    res = (res + dfs(v, f - cost)) % MOD
            memo[u][f] = res
            return res

        return dfs(start, fuel)

思路 1：复杂度分析

• 时间复杂度：$O(n^2 \times fuel)$，$n \le 100$，$fuel \le 200$，约 $2 \times 10^6$ 次操作。
• 空间复杂度：$O(n \times fuel)$，记忆化数组。

---

思路 2：自底向上 DP（递推）

1. 核心思想

自底向上的 DP 按油量从小到大递推。定义 $dp[f][u]$ 为使用恰好 $f$ 油量到达城市 $u$ 的路径数（从 $start$ 出发）。

2. 具体步骤

第 1 步：初始化 $dp[0][start] = 1$（油量 $0$ 时在 $start$ 有一条路径）。

第 2 步：遍历油量 $f$ 从 $0$ 到 $fuel$：

• 遍历当前城市 $u$，如果 $dp[f][u] > 0$：
  • 遍历下一个城市 $v \neq u$：
    • $cost = |locations[u] - locations[v]|$。
    • 若 $f + cost \le fuel$：
      • $dp[f + cost][v] = (dp[f + cost][v] + dp[f][u]) \% MOD$。

第 3 步：最终结果 $ans = \sum_{f=0}^{fuel} dp[f][finish]$。

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        MOD = 10 ** 9 + 7
        n = len(locations)
        dp = [[0] * n for _ in range(fuel + 1)]
        dp[0][start] = 1

        for f in range(fuel + 1):
            for u in range(n):
                if dp[f][u] == 0:
                    continue
                for v in range(n):
                    if v == u:
                        continue
                    cost = abs(locations[u] - locations[v])
                    if f + cost <= fuel:
                        dp[f + cost][v] = (dp[f + cost][v] + dp[f][u]) % MOD

        ans = sum(dp[f][finish] for f in range(fuel + 1)) % MOD
        return ans

思路 2：复杂度分析

• 时间复杂度：$O(n^2 \times fuel)$。
• 空间复杂度：$O(n \times fuel)$。