千问 LeetCode 1575.统计所有可行路径 public int countRoutes(int[] locations, int start, int finish, int fuel)

这是一道经典的动态规划记忆化搜索问题。我们需要计算从起点城市到终点城市在给定油量限制下的所有可行路径数量。 核心思路1. 状态定义我们定义 dp[i][f] 表示当前在城市 i剩余油量为 f 时到达终点城市 finish 的路径总数。2. 状态转移在城市 i 且剩余油量为 f 时我们可以尝试前往任意一个其他城市 jj ! 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 是一个非常有效的优化。虽然不写也能过但在数据量较大时能显著减少递归次数。