千问 LeetCode 1575.统计所有可行路径 public int countRoutes(int[] locations, int start, int finish, int fuel)
这是一道经典的动态规划（记忆化搜索）问题。我们需要计算从起点城市到终点城市，在给定油量限制下的所有可行路径数量。
🧠 核心思路
1. 状态定义：
我们定义 dp[i][f] 表示：当前在城市 i，剩余油量为 f 时，到达终点城市 finish 的路径总数。
2. 状态转移：
在城市 i 且剩余油量为 f 时，我们可以尝试前往任意一个其他城市 j（j != i）。
* 计算从 i 到 j 的油耗：cost = |locations[i] - locations[j]|。
* 如果 f >= cost，说明油量足够，我们可以从 j 继续走。此时的路径数为 dp[j][f - cost]。
* 将所有可能的 j 的路径数累加。
3. 边界条件（关键点）：
* 到达终点：如果当前城市 i 就是终点 finish，那么即使不继续移动，也已经找到了一条可行路径（即停在原地）。因此，初始路径数设为 1。
* 油量耗尽：如果油量为 0 且无法移动到任何其他城市，则路径数为 0（除非已经在终点，这由上一条规则处理）。
4. 优化（剪枝）：
如果从当前城市 i 到终点 finish 的最短距离（直线距离）都大于剩余油量 f，那么无论怎么走都不可能到达终点，直接返回 0。
💻 代码实现
class Solution {
// 定义模数，防止结果溢出
int MOD = 1000000007;
// 记忆化数组：memo[i][f] 表示在城市 i，剩余油量 f 时到达终点的路径数
// 初始化为 -1 用于区分“结果为0”和“尚未计算”
int[][] memo;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
int n = locations.length;
// 初始化记忆化数组
memo = new int[n][fuel + 1];
for (int i = 0; i fuel) {
memo[curr][fuel] = 0;
return 0;
}
// 3. 初始化结果
// 如果当前就在终点，算作一条路径（即停留在这里）
int paths = (curr == finish) ? 1 : 0;
// 4. 尝试前往其他所有城市
for (int next = 0; next = cost) {
paths += dfs(locations, next, finish, fuel - cost);
paths %= MOD; // 取模防止溢出
}
}
// 5. 记录并返回结果
memo[curr][fuel] = paths;
return paths;
}
}
📊 复杂度分析
* 时间复杂度：O(N² × F)
* 其中 N 是城市数量，F 是油量。
* 我们需要计算 N × F 个状态。对于每个状态，我们需要遍历 N 个可能的下一个城市。
* 空间复杂度：O(N × F)
* 主要用于存储 memo 记忆化数组以及递归调用栈的深度。
💡 关键点解释
1. 为什么 curr == finish 时 paths 初始化为 1？
题目允许经过任意城市多次。如果你到达了终点，你可以选择停止（这是一条路径），也可以选择继续去别的城市逛逛再回来。因此，只要到达终点，就至少贡献了 1 条路径。
2. 为什么要用 memo？
这是一个典型的重复子问题。例如，你可能通过路径 A -> B -> C 到达城市 C 剩 5 单位油，也可能通过路径 D -> E -> C 到达城市 C 剩 5 单位油。如果不记忆化，计算从 C 出发的路径数会被重复执行多次。
3. 剪枝的作用：
代码中的 Math.abs(locations[curr] - locations[finish]) > fuel 是一个非常有效的优化。虽然不写也能过，但在数据量较大时能显著减少递归次数。