最近在刷动态规划专题碰到 LeetCode 1928 这道『规定时间内到达终点的最小花费』第一眼以为是个最短路变种看完数据范围才发现是典型的二维动态规划。题目同时把“时间”和“费用”两个约束压在一条路径上想直接套 Dijkstra 会在状态设计上绕半天但把时间当成状态维度用 dp[t][v] 表示走到城市 v 时用掉的时间一层层往下递推整个思路就非常顺了。这篇文章把这道题的状态设计、转移方程、代码实现、复杂度分析以及我刷题时踩过的几个坑完整记录下来。如果你正在刷 LeetCode 动态规划或者准备面试时碰到这种“带资源上限的图上最短路”问题这篇应该能帮你少走不少弯路。1. 题目场景与核心思路1.1 题目到底在问什么题目给定 n 个城市编号从 0 到 n-1每个城市有一个通行费 passingFees[i]只要经过这个城市就要交一次钱起点和终点都算。给定一个无向图每条边连接两个城市并且有一个正整数的通行时间。再给定一个总的时间上限 maxTime要求从城市 0 出发在不超过 maxTime 的时间内到达城市 n-1求最小的通行费总和。如果根本到不了返回 -1。把问题抽象一下其实是一个带节点费用的无向带权图边权是时间节点权是费用。要找一条从 0 到 n-1 的路径限制条件是总边权之和不超过 maxTime优化目标是路径上所有经过节点的权值之和最小。这里有个容易被忽略的细节重复经过同一个城市通行费是要重复计算的不是只算一次。数据范围方面n 最多 1000maxTime 最多 1000passingFees 是正整数边时间也是正整数。这个范围很关键它直接决定了动态规划是可行的后面我会专门展开。1.2 为什么不能直接套最短路模板很多人的第一反应是跑 Dijkstra按费用作为优先级每次扩展费用最小的城市。这个思路在只有一个目标值的图上是正确的但这道题有两个互相制约的指标时间和费用。走一条边会同时消耗时间也会因为进入新城市而增加费用。如果只按费用扩展你可能找到一条费用很低的路径但它消耗的时间已经超过 maxTime反过来如果只按时间扩展最短时间的路径费用可能很高。单目标最短路算法没有办法同时表达“时间不超过上限”和“费用尽量小”这两个条件。有人会说那我在 Dijkstra 的 state 里同时记录 (城市, 当前时间) 不就行了确实可以但这就变成了二维状态图节点数量变成了 n × maxTime本质上就是在做动态规划。既然绕来绕去都会回到二维状态不如直接按时间维度枚举用 DP 一层层推逻辑还更直白。1.3 数据范围决定 DP 可行性这道题能直接用动态规划核心原因是 maxTime 上限只有 1000。时间是一个天然的“阶段”维度dp 数组开成 (maxTime1) 行、n 列最多约 100 万个状态内存和运行时间都非常可控。如果 maxTime 放大到 10^9这种二维 DP 连数组都开不下那就得换思路比如把城市和时间组合成一个大图用 Dijkstra 在状态图上做搜索并配合剪枝。但在这道题的数据范围下老老实实按时间递推就是最优解。我自己的经验是做题先看数据范围。看到 maxTime 这种“小容量上限”第一反应就应该是把容量拉进状态里做 DP如果容量特别大再考虑转化成最短路问题。这道题就是典型的“容量足够小状态可以枚举”。2. 状态设计与转移方程2.1 状态定义把时间塞进 DP 维度定义二维数组 dp[t][v] 表示恰好花费 t 分钟到达城市 v 时最小的通行费总和。这里用“恰好”这个词而不是“不超过”是有讲究的。题目只要求总时间不超过 maxTime如果你提前到达了某个城市后续站在原地等待并不会产生额外费用。如果我用“恰好”定义那么提前到达的信息会保留在更小的 t 那一层最后答案扫描所有 t ≤ maxTime 取最小值就能把“提前到达后等待”的情况覆盖进来。反过来如果用“不超过 t 分钟到达 v”来定义那每一层都要额外把 dp[t-1][v] 继承到 dp[t][v]相当于多了一次城市维度的更新。两种定义最终得到的答案等价但“恰好”定义的转移式子更干净不用等一个等待状态。我下面的推导和代码都按“恰好”来写。还有一点dp[0][0] 必须初始化为 passingFees[0]因为从城市 0 出发人已经站在城市 0 里了出发前就要先交这个城市的通行费。其他所有 dp[0][v] 都是 INF表示时间 0 时不可能到达其他城市。2.2 初始化和转移方程转移方程可以写成如果存在一条无向边 (u, v) 边权为 w并且 t ≥ w那么dp[t][v] min(dp[t][v], dp[t-w][u] passingFees[v])同时因为边是无向的从 v 走到 u 也要更新dp[t][u] min(dp[t][u], dp[t-w][v] passingFees[u])解释一下每个部分的含义。dp[t-w][u] 表示用 t-w 分钟到达城市 u 的最小费用这个费用已经包含了城市 u 的通行费。现在从 u 走一条边到 v耗时 w恰好凑满 t 分钟进入城市 v 需要再交 passingFees[v]所以总费用是 dp[t-w][u] passingFees[v]。为什么要同时更新两个方向因为题目给的是无向边你可以从 u 到 v也可以从 v 到 u。如果只写一个方向遇到需要反向行走的路径就会出错这是这道题最容易踩的坑之一。为什么要按 t 从小到大枚举因为每条边的 w 都是正整数所以 t-w 一定小于 t。dp[t] 层只依赖更早的层不会同层循环依赖满足无后效性。这也是动态规划能够直接使用的原因。2.3 手工推演小例子为了把转移过程讲清楚我构造一个非常小的例子手动跑一遍。假设 n 3城市编号 0、1、2passingFees [5, 10, 20]edges [[0, 1, 3], [1, 2, 4], [0, 2, 10]]maxTime 10。也就是说从 0 到 1 耗时 3从 1 到 2 耗时 4从 0 直接到 2 耗时 10。初始化 dp[0][0] 5。t 3 时遍历到边 [0, 1, 3]可以更新 dp[3][1] dp[0][0] passingFees[1] 5 10 15。同时反向更新 dp[3][0]但 dp[0][1] 是 INF所以不生效。t 7 时遍历到边 [1, 2, 4]可以更新 dp[7][2] dp[3][1] passingFees[2] 15 20 35。t 10 时遍历到边 [0, 2, 10]可以更新 dp[10][2] dp[0][0] passingFees[2] 5 20 25。把部分层打印出来tdp[t][0]dp[t][1]dp[t][2]05INFINF3INF15INF7INFINF3510INFINF25最后答案取所有 t ≤ 10 中 dp[t][2] 的最小值min(35, 25) 25正确。这个例子还能说明一个细节dp[10][1] 仍然是 INF因为没有任何一条路径恰好用 10 分钟到达城市 1。但用 3 分钟到过城市 1费用 15这个信息保存在 dp[3][1] 里。如果终点是城市 1最后扫描所有 t 就能把 15 这个答案捞出来直接返回 dp[10][1] 就会漏掉。3. 代码实现与复杂度分析3.1 C 参考实现下面给出完整的 C 实现注释写得比较细。class Solution { public: int minCost(int maxTime, vectorvectorint edges, vectorint passingFees) { int n passingFees.size(); const int INF INT_MAX / 2; // dp[t][v]恰好用 t 分钟到达城市 v 的最小通行费 vectorvectorint dp(maxTime 1, vectorint(n, INF)); dp[0][0] passingFees[0]; // 起点也要交费 for (int t 1; t maxTime; t) { for (const auto e : edges) { int u e[0], v e[1], w e[2]; if (t w) continue; // 时间不够走这条边 // 从 u 走到 v进入 v 要交 passingFees[v] if (dp[t - w][u] ! INF) { dp[t][v] min(dp[t][v], dp[t - w][u] passingFees[v]); } // 无向边从 v 走到 u if (dp[t - w][v] ! INF) { dp[t][u] min(dp[t][u], dp[t - w][v] passingFees[u]); } } } // 因为“恰好 t 分钟”可能早于 maxTime 到达所以全部取 min int ans INF; for (int t 0; t maxTime; t) { ans min(ans, dp[t][n - 1]); } return ans INF ? -1 : ans; } };代码本身不复杂。外层循环枚举时间内层循环枚举所有边对每条边做两个方向的转移。时间复杂度不算高数据范围内完全能跑。有个小细节INF 我用的是 INT_MAX / 2不是 INT_MAX。因为后面要做 dp[t-w][u] passingFees[v]如果 dp 值是 INT_MAX加一个正数会溢出成负数反而可能错误地更新答案。用 INT_MAX / 2 可以保证即使加上最大费用也不会溢出。3.2 Python 简洁实现Python 版本写起来更短思路完全一致。注意 INF 用大整数比如 10**18就不会有溢出问题。class Solution: def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) - int: n len(passingFees) INF 10**18 dp [[INF] * n for _ in range(maxTime 1)] dp[0][0] passingFees[0] for t in range(1, maxTime 1): for u, v, w in edges: if t w: dp[t][v] min(dp[t][v], dp[t - w][u] passingFees[v]) dp[t][u] min(dp[t][u], dp[t - w][v] passingFees[u]) ans min(dp[t][n - 1] for t in range(maxTime 1)) return ans if ans INF else -1Python 版没有显式判断 dp[t-w][u] 是否为 INF因为 INF 是 10^18加上 passingFees 后仍然是很大的数不会成为最小值。这个写法更简洁但要是 INF 设小了也可能出错所以还是建议用足够大的数。3.3 复杂度分析与扩展优化时间复杂度方面外层循环时间 t 从 1 到 maxTime内层循环每条边。每条边在每次时间层都会被访问一次并且做两个方向的更新所以总复杂度是 O(maxTime × m)m 是边数。空间复杂度是 O(maxTime × n)存储 dp 数组。这个复杂度在同类型题里算很好的了尤其是 maxTime 只有 1000 的前提下。内存方面(1001 × 1000) 个 int大约 4MB完全无压力。有人会问能不能滚动数组优化空间。这题不太适合滚动数组因为 dp[t][v] 依赖的是 dp[t-w][u]w 是任意正整数等于说需要随机访问任意历史层的数据。只保留上一层的滚动数组没法满足这种随机访问需求。不过既然二维数组本身也只有 4MB就没必要为了省空间增加复杂度。如果遇到 m 特别大的稠密图比如边数接近 n^2那 O(maxTime × m) 可能会比较紧张。这时候可以考虑用邻接表实现状态转移时只遍历当前城市的邻居复杂度写成 O(maxTime × (n m)) 更好看但本质还是同一个东西。再极限一点可以用 Dijkstra 在 (城市, 时间) 状态图上跑不过代码复杂度会明显上升一般面试和竞赛里这道题用二维 DP 就足够了。4. 常见坑点与排查技巧4.1 INF 的选择与溢出隐患这个问题在很多图论 DP 里都会遇到。如果 INF 直接设成 INT_MAX在 C 里做 dp[t-w][u] passingFees[v] 时只要 dp[t-w][u] 是 INT_MAX结果就会溢出成负数导致一个错误的小值被写进 dp[t][v]后面全乱套。解决方式很简单用 INT_MAX / 2 或者 1e9 这种明显大于答案上界的数作为 INF。这题路径最多经过 maxTime 条边每条边费用最多 1000总费用上限大概 10^6 级别所以 1e9 足够安全。调试的时候可以加一句输出看看 dp 数组里有没有出现负数有的话基本就是 INF 溢出了问题。4.2 无向边一定要更新两个方向这是最容易混淆的坑。题目给的 edges 是无向边意味着可以从 u 到 v也可以从 v 到 u。很多写法只写了从 u 到 v 的转移提交后可能样例过了但一旦最优路径需要反向走就会答案错误。判断这种问题最快的办法是构造一个对称的简单图比如 0-1-2 的链看 0 到 2 的路径是否只需要正向边改成需要先走反向边的图再测一次。如果 DP 结果不对先检查这里。更稳妥的做法是在写边转移之前先在设计状态时想清楚“这是一条无向边”然后下意识地写出两个方向的更新。或者干脆建邻接表遍历两个方向的邻接关系不容易漏。4.3 “恰好”与“不超过”的答案差异我主推的是“恰好用 t 分钟到达”的状态定义所以最后答案必须把 t 从 0 到 maxTime 全部扫描一遍取最小值。如果你直接返回 dp[maxTime][n-1]遇到最优路径提前到达的情况就会出错。网上有些题解直接返回 dp[maxTime][n-1]是因为他们的 dp 定义是“不超过 t 分钟到达”并且在每一层做了等待继承dp[t][v] min(dp[t][v], dp[t-1][v])。这种情况下dp[maxTime][n-1] 确实包含了所有更早到达的状态。两种写法等价但千万别混用。我建议你在自己写的时候固定一种然后在注释里写明自己的定义这样即使隔几天回来看代码也不会晕。4.4 重复收费与起点费用题目说每经过一个城市都要交通行费注意是“每经过一次”都要交。如果路径从城市 0 出发绕了一圈又回到城市 0再离开那么城市 0 的通行费要交两次。这个逻辑在转移方程里是自然成立的。dp[t-w][u] 里已经包含了城市 u 的通行费从 u 跨到 v 时再加上 passingFees[v]就是进入 v 的又一次计费。反向走同理。唯一要小心的是初始化dp[0][0] 必须是 passingFees[0]不能是 0。如果把起点费用漏掉最终答案会凭空少一个 passingFees[0]。4.5 调试技巧打印 DP 表最后分享一个我自己常用的调试方法遇到 DP 题答案不对不要盯着代码发呆直接在关键位置把 dp 数组打印出来。对于这道题可以在每次 t 循环结束后把 dp[t] 那一整行打出来看看哪些城市可达费用分别是多少。对比自己手动推演的小例子很容易定位是哪一层转移出了问题。还可以写一个暴力 DFS在数据规模很小的时候枚举所有不超过 maxTime 的路径和 DP 结果对拍。路径数不多时暴力法虽然慢但结果一定正确拿来验证 DP 边界非常好使。边界测试也要记得覆盖maxTime 0、n 1、起点就是终点、图不连通等情况。最后说一点实战体会刷完这道题我最大的感受是这类“两个指标 一个容量上限”的图上问题几乎都可以把容量拉进状态做二维 DP。时间上限小就把时间当外层维度油量上限小就把油量当外层维度。关键是要意识到单目标最短路解决不了这种双约束问题必须给状态加一个维度。我在第一次做的时候就是被 Dijkstra 带偏了想着怎么在优先队列里同时比较时间和费用折腾了半天没写对。后来退一步把时间直接枚举出来用 DP 一层层推十分钟就写完了。所以遇到这个题型多想想状态定义比急着套最短路模板要高效得多。希望这篇题解能帮你把这道题彻底拿下。