LeetCode 1575. 统计所有可行路径
目录
题目描述
题意分析
数轴上有
n座城市，locations[i]是第i座城市的坐标。从start出发、油箱里有fuel升油，每次可以开到任意一座不同的城市，耗油量等于两地坐标差的绝对值。问总共有多少条不同的路径能到达finish，答案对 $10^9 + 7$ 取模。有几处措辞必须抠死。第一，路径可以经过
finish之后继续开走再回来，只要最终停在finish就算数——所以到达finish不是终止条件，而是一个可以「记一笔」但仍要继续展开的时刻。第二，城市可以重复访问，路径长度没有上限，唯一的限制是油量。第三，start可以等于finish，此时「原地不动」本身就是一条合法路径。既然能反复往返，路径条数是可以爆炸的，这解释了为什么要取模。
约束给得很克制：
n不超过 100，fuel不超过 200。两者相乘只有两万，这个数字明确指向「以（当前城市，剩余油量）为状态」的动规——状态数两万，每个状态枚举 100 个下一站，总计两百万次转移，绰绰有余。反过来，若按路径去搜索则是指数级，必然超时。油量单调递减是这个问题能被拆解的根本原因：任意一次移动都严格消耗至少 1 升油（城市坐标互不相同），所以状态不会成环，递归一定会终止。
边界上，油量耗尽时若恰好停在
finish计 1 条，否则计 0 条；start == finish时初始状态就贡献 1。
解法：记忆化搜索
核心思路
定义
dfs(city, remain)：当前位于city、剩余remain油量时，最终停在finish的路径数。后续选择只由这两个量决定，因此用二维记忆表缓存。若
city == finish，当前立即停止就是一条路径，所以初值为 1；但不能直接返回，因为还可以离开终点再回来。随后枚举所有其他城市，移动费用不超过剩余油量时，累加下一状态的答案。燃料单调性：坐标互不相同，每次移动费用至少为 1，递归中的
remain严格减小。因此状态图无环，不需要城市访问标记，也不会无限递归。不变量：
memo[city][remain]一旦写入，就等于从该状态出发的完整合法路径数，并已按模数归一化。正确性：任意合法路径要么在当前终点立即结束，要么选择唯一的第一站，再接上一条对应子状态的合法路径。转移枚举所有付得起费用的第一站，分类互斥且完整；记忆化只复用相同状态结果，不改变计数。
解题步骤
- 创建
n x (fuel+1)的缓存并填为-1，区分“未计算”和合法答案 0。- 递归入口先查缓存；当前位置是终点时令答案初值为 1，但继续枚举移动。
- 枚举不同的下一城市，计算坐标绝对差；费用不超过剩余油量才递归。
- 每次累加后取模，写入缓存并返回。
locations=[2,3,6,8,4]、start=1、finish=3、fuel=5有 4 条路径，包括直达以及经城市 2、4 的组合。边界
start==finish时空路径先贡献 1，但仍需统计有油时离开再返回的路线。locations=[1,2]、油量 1 时，恰好耗尽到达终点也必须计入。
代码实现
class Solution {
private static final int MOD = 1_000_000_007;
private int[] loc;
private int finish;
private int[][] memo;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
this.loc = locations;
this.finish = finish;
int n = locations.length;
memo = new int[n][fuel + 1];
for (int i = 0; i < n; i++) {
for (int f = 0; f <= fuel; f++) {
memo[i][f] = -1;
}
}
return dfs(start, fuel);
}
private int dfs(int pos, int fuel) {
if (memo[pos][fuel] != -1) {
return memo[pos][fuel];
}
long answer = 0;
if (pos == finish) {
answer = 1;
}
for (int next = 0; next < loc.length; next++) {
if (next == pos) {
continue;
}
int cost = Math.abs(loc[pos] - loc[next]);
if (cost <= fuel) {
answer += dfs(next, fuel - cost);
answer %= MOD;
}
}
memo[pos][fuel] = (int) answer;
return memo[pos][fuel];
}
}
func countRoutes(locations []int, start int, finish int, fuel int) int {
const mod = 1_000_000_007
n := len(locations)
memo := make([][]int, n)
for i := 0; i < n; i++ {
memo[i] = make([]int, fuel+1)
for f := 0; f <= fuel; f++ {
memo[i][f] = -1
}
}
var dfs func(pos int, fuel int) int
dfs = func(pos int, fuel int) int {
if memo[pos][fuel] != -1 {
return memo[pos][fuel]
}
answer := 0
if pos == finish {
answer = 1
}
for next := 0; next < n; next++ {
if next == pos {
continue
}
cost := locations[pos] - locations[next]
if cost < 0 {
cost = -cost
}
if cost <= fuel {
answer += dfs(next, fuel-cost)
answer %= mod
}
}
memo[pos][fuel] = answer
return answer
}
return dfs(start, fuel)
}
复杂度分析
- 时间复杂度：$O(n^2 \cdot fuel)$。共有 $O(n \cdot fuel)$ 个状态，每个状态枚举
n个下一站。- 空间复杂度：$O(n \cdot fuel)$ 用于缓存；递归栈深度至多为
fuel。
关键点总结
- 状态是“当前城市 + 剩余油量”，历史访问顺序不影响后续选择。
- 到达终点只是多一种“现在结束”的选择，不能终止搜索。
- 坐标互异保证每次移动严格耗油，状态不会成环。
- 缓存哨兵必须用
-1，因为 0 是合法路径数。- 城市允许重复访问，不能使用普通图搜索的
visited。
易错点总结
- 到达
finish就return 1：会漏掉离开终点再返回的合法路径。- 允许
next==city：产生零油耗自调用，递归无法终止。- 距离不取绝对值：向坐标较小的城市移动会得到负费用。
- 使用
cost<remain：恰好耗尽燃料到达终点的路径被漏掉。- 缓存第二维长度只开
fuel：初始状态访问下标fuel时越界。- 添加城市级
visited：合法路线可以重复经过同一城市，会被错误剪掉。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 576. 出界的路径数 | 中等 | 状态是（位置，剩余步数），计数目标改为走出边界，转移只有四个方向 |
| 1155. 掷骰子等于目标和的方法数 | 中等 | 状态是（骰子数，剩余目标和），资源同样单调递减，是本题的一维版 |
| 62. 不同路径 | 中等 | 转移方向单一且无资源维度，可用组合数直接闭式求解 |
| 63. 不同路径 II | 中等 | 在计数基础上加入障碍物，考的是不可达状态的初始化 |
| 980. 不同路径 III | 困难 | 要求恰好走遍所有空格，状态需用位掩码记录访问集合，无法只靠资源量 |
| 787. K 站中转内最便宜的航班 | 中等 | 同为「位置 + 剩余额度」的二维状态，但目标从计数换成最小化代价 |
| 322. 零钱兑换 | 中等 | 单维资源递减的最优化问题，适合对比自顶向下与自底向上的写法 |