刷算法题的人应该都见过这么一类题目给一张带权图限制一个资源上限让你在满足限制的前提下求另一个指标的最值。LeetCode 1928 这道「规定时间内到达终点的最小花费」就是非常典型的代表它把图论的路径搜索和动态规划的时间维度状态合并在一起既考验你对状态定义的理解也考验代码实现时对边界的敏感度。我刷这道题的时候卡了两次一次是初始化没想清楚一次是双向边拆开之后漏了对反向路径的处理后面把 DP 状态一理顺发现整个题其实非常清爽。这篇文章会把这道题的完整思路、状态设计、递推公式、代码实现、复杂度分析全部拆开讲还会把我实际踩过的坑和网上常有人问的细节一并整理出来。适合三类读者正在准备算法面试、刷 DP 和最短路径变种题的选手学动态规划但总是想不明白为什么用时间维度 城市维度建状态的初学者以及想快速看懂题解、不想被各种混淆写法绕晕的备赛党。1. 题目到底在问什么图上的双约束优化1.1 题意还原与输入输出结构先把这个题剥成最朴素的描述有n个城市编号从0到n-1每个城市有一个通行费记作passingFees[i]你经过这个城市就要付费。城市之间有若干条双向道路每条路都需要消耗一定时间。你现在从城市0出发要在不超过maxTime的时间内到达城市n-1求所有合法路线中通行费总和的最小值。如果根本不可能在规定时间内到达就返回-1。输入结构一般长这样maxTime一个整数表示允许的最大总耗时edges[i] [u, v, t]表示城市u和v之间有一条耗时为t的双向道路passingFees[i]表示进入城市i需要支付的费用起点和终点都算。费用和时间这两个约束是同时存在的时间超过maxTime的路径直接非法费用不是唯一的优化目标必须在合法时间内取费用最小。这种模型在现实中很常见比如规划一次跨城市出行既要在预算时间内到达又想尽量省钱或者外卖配送、物流调度这类场景时间窗口是硬条件成本是软目标。1.2 为什么是动态规划而不是普通最短路很多人第一反应是直接 Dijkstra。确实如果只求最短时间或者只求最小费用Dijkstra 都是标准解法。但这里的问题是双指标优化一个指标是时间一个指标是费用。Dijkstra 的贪心逻辑要求堆顶元素一旦出队它的答案就是最终最优的不过这个性质在这里的前提是每一条边增加的费用 / 时间是固定的优化目标唯一。可这道题里时间有硬上限费用是另一个维度你没法保证从堆顶取出的费用最小的点最后真的能走到终点因为它可能早就超时了同理时间最小的点也不一定费用最优。举个例子你就明白了一条直达道路时间刚好等于maxTime费用很高另一条绕路的路径时间短但费用低。如果只看当前时间最短的节点去贪心可能选了那条绕路却错过直达的合法方案。DP 则不一样它把所有可能的时间点 城市都拆成独立状态逐个枚举转移保证不会漏掉任何一条路径也不会因为贪心顺序丢失正确性。所以这道题的核心识别标志就是有个约束维度时间 一个优化维度费用且约束维度的上限不大。只要maxTime在可控范围内dp[t][v]这种二维状态就是最自然的解法。2. 动态规划的核心状态设计、转移方程与无后效性2.1 状态定义dp[t][v] 的含义与合理性要解决双约束问题最常见的套路就是把其中一个维度放进状态里让另一个维度成为 DP 的值。这里我把时间作为状态维度定义dp[t][v]表示恰好在时间t到达城市v时能取到的最小通行费总和。为什么要用恰好而不是不超过这是个很关键的理解点。如果你定义成在时间不超过 t 时到达城市 v 的最小费用那么转移的时候你很难判断当前节点接下来的时间余量到底是多少状态之间会相互污染。而定义成恰好之后时间信息就被精确地记录在状态里后面转移只需要加上w就能得到新的时间点逻辑非常干净。初始化也很直观dp[0][0] passingFees[0]表示在时间0从城市0出发此时已经支付了出发城市0的通行费。其余所有状态初始化为一个很大的数代表不可达。这里需要多嘴一句有的题解会把起点费用延后到转移时再加导致最后答案计算时处理起来很绕。我实际写下来感觉最不容易出错的写法就是起点费用在初始化就计入之后每转移到一个新城市v额外加上passingFees[v]即可。这样答案直接就是dp[t][n-1]的最小值。2.2 转移方程枚举边、累加时间与费用有向边和无向边的处理不太一样。解题目里明确说Here,edges[i] [u, v, time_i]denotes a bidirectional road所以每一条边要拆成两条方向来处理不然你会漏掉v - u的转移。假设当前状态是dp[t][u]它表示在时间t到达城市u的最小花费。从u出发走一条到v、耗时为w的边新的时间就是t w。如果t w maxTime说明这条路还在时间限制内那么到达v的总费用就是dp[t][u] passingFees[v]用这个值去尝试更新dp[tw][v]取最小值dp[tw][v] min(dp[tw][v], dp[t][u] passingFees[v])写成循环就是外层枚举所有时间t内层遍历所有城市u再内层遍历u的所有邻接边。如果某个dp[t][u]还是初始的无穷大说明在时间t根本无法到达u直接跳过即可。注意这里不需要做像 Bellman-Ford 那样备份当前轮状态的操作。因为每条边的耗时w至少为 1所以dp[tw][v]的更新只会影响未来更大的时间点绝不会反过来影响当前时间t下的其他状态。时间递增的外层循环天然保证了这种无后效性。最终答案就是所有dp[t][n-1]中的最小值。如果这个最小值依然是无穷大说明在规定的maxTime内根本走不到终点返回-1。2.3 时间维度的选择为什么是时间而不是城市有人会问那我定义成dp[v]表示到达城市v的最小费用用类似 SPFA 的方式迭代行不行理论上可以但你需要额外记录每个城市当前的最短到达时间否则没法判断叠加时间后是否超限。这么做不仅状态本身仍然要带着时间信息而且由于这个题没有负权边你用 SPFA 式的反复松弛反而容易陷入无效更新。把时间作为第一维还有一个很好的性质你不需要对城市之间的到达顺序做拓扑排序因为时间是天然有序的。哪怕图里有环比如0 - 1 - 0 - 1每走一步时间都会增加所以环不会导致状态重复只会被时间上限自然拦截。这也是为什么这类限制步数 / 限制时间 / 限制点数的题目都会导向 DP 而不是纯图搜索。maxTime的规模决定了这个做法是否可行。LeetCode 1928 的maxTime一般在几千以内n也不会特别大所以二维数组 (maxTime 1) * n是完全能开的。如果哪天maxTime特别大比如 10^9那 DP 的空间和时间就彻底炸了那种情况得换思路比如分层图上做剪枝搜索这是后话至少这个题的标准解法就是二维 DP。3. 代码实现与完整过程3.1 建图细节双向边要拆成两条单向边实现前先把图建好。拿到edges之后对每一条[u, v, w]在u的邻接表里加上(v, w)同时在v的邻接表里加上(u, w)。这里有个常见的低级错误只建了一条方向导致从0出发的路径一旦需要走反向边就全部断掉答案直接变成-1还不容易排查。所以我建议建图后顺手检查几个样例比如0 - 1和1 - 2这种链路确保两个方向都在邻接表里。如果不想用邻接表也可以直接在 DP 循环里遍历所有边对每条边做两个方向的转移如果 dp[t][u] 可达则尝试更新 dp[tw][v] 如果 dp[t][v] 可达则尝试更新 dp[tw][u]这种写法代码更短但每次都要扫一遍全部边效率略低。数据规模小的时候无所谓数据规模大的时候邻接表明显更高效因为很多边和当前不可达的城市根本无关。每种语言写起来稍有差别但结构完全一样。我用 C 写了一个参考实现就是讲思路时说的那种标准写法class Solution { public: int minCost(int maxTime, vectorvectorint edges, vectorint passingFees) { int n passingFees.size(); // INF 要比任何可能的费用总和都大 const int INF 1e9 7; // dp[t][v]恰好时间 t 到达城市 v 的最小通行费 vectorvectorint dp(maxTime 1, vectorint(n, INF)); // 起点城市 0 的费用在初始时就计入 dp[0][0] passingFees[0]; // 建邻接表双向道路拆成两条单向边 vectorvectorpairint, int graph(n); for (const auto e : edges) { int u e[0], v e[1], w e[2]; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } // 按时间递增枚举所有状态 for (int t 0; t maxTime; t) { for (int u 0; u n; u) { if (dp[t][u] INF) continue; // 尝试从 u 走向所有邻居 v for (const auto [v, w] : graph[u]) { int nextTime t w; if (nextTime maxTime) continue; dp[nextTime][v] min(dp[nextTime][v], dp[t][u] passingFees[v]); } } } // 答案是所有时间内到达终点 n-1 的最小费用 int ans INF; for (int t 0; t maxTime; t) { ans min(ans, dp[t][n - 1]); } return ans INF ? -1 : ans; } };这段代码提交是能过的而且我觉得它的可读性比一些压缩过变量的版本要好得多很适合作为面试时的板子。3.2 模拟一次转移过程一个具体的小例子空讲公式容易晕我跑一个小例子说明递推到底是怎么发生的。假设有 3 个城市0、1、2通行费分别是[5, 10, 20]道路和时间0 - 1耗时21 - 2耗时30 - 2耗时5maxTime 5。起点0在时间0的复杂度是dp[0][0] 5。先处理时间t 0城市0可达。走0 - 1时间变成2费用变为5 10 15所以dp[2][1] 15。走0 - 2时间变成5费用变为5 20 25所以dp[5][2] 25。再处理t 2城市1可达费用15。走1 - 2时间变成2 3 5费用变为15 20 35所以尝试更新dp[5][2]但已有的25更小因此不更新。最后在时间0 到 5里找到达2的最小值答案是25对应的是0直达2那条路。这个例子的意义在于演示即使绕路的两段拼起来也能在时限内到达DP 依然会老老实实比较两条路线的费用然后取更小的那个。不像贪心算法DP 不会因为某条路径看起来耗时少就草率地认定它最优。3.3 时间复杂度和空间复杂度分析时间上外层循环maxTime 1次内层先遍历n个城市再遍历每个城市的度。总复杂度理论上可以认为是O(maxTime * (n E))其中E是双向边拆开后的边的总数也就是edges.size() * 2。代码里我用的是邻接表所以整张图被完整扫描一遍的总次数就是maxTime * (n E)这个量级。空间上开了一个maxTime 1行、n列的二维数组因此空间复杂度是O(maxTime * n)。以maxTime 1000、n 1000为例1001 * 1000个int大约是 4MB 左右完全能轻松放进内存。曾有读者问我能不能滚动数组优化空间把dp[t]这一维滚动掉。结论是可以的但有一定代价。因为一条边的耗时可能不同你从dp[t]转移到的dp[tw]不一定就是下一层而可能是下很多层。如果只保存最近一层的dp那么在时间t之后某个时间点回来更新时原来的状态可能已经被覆盖了。所以真要滚动需要使用一个待更新队列或者借助类 Dijkstra 的搜索方式这就已经偏离 DP 的简洁形态了。实际面试或比赛中maxTime * n的二维数组通常可以接受所以我更推荐先写不优化的版本保证正确性优先然后再谈优化。4. 常见问题与排查技巧实录4.1 初始化与 INF 的选取这题的坑往往不出在转移上而出在最不起眼的地方。初始化时dp数组要全部填成一个很大的数我习惯用1e9 7或INT_MAX / 2。INT_MAX直接用来加会导致整型溢出所以不要图省事用INT_MAX去累加。INT_MAX / 2也可以只要确保任何合法费用和INF相加之后仍然远大于真实答案即可。另一个隐蔽的问题是起点城市 0 的费用到底要不要算进去题目原文写的是 including the starting and ending cities所以一定要算。如果写题解时把这个地方看漏样例可以通过但换一组数据就出问题。以n 1为例起点就是终点费用就是passingFees[0]不管maxTime是多少答案都应该是passingFees[0]。这个边界用例很适合用来验证你的初始化有没有写错。4.2 什么时候返回 -1 才算对返回 -1 的场景只有一种在maxTime时间内无论如何都到不了终点。但很多人在实现时把答案不存在和dp 仍是 INF搞混导致多写了不必要的时间判断。比如有些题解会在每一轮时间结束后检查dp[t][n-1]有没有变小如果没有就提前退出循环。这个优化要小心使用因为存在多个不同时间点到达终点的情况比如直达在t5到达费用 30绕路在t3到达费用 20。如果只看单一时间点身后的变化可能会误判而实际上其他时间点还有更优解。我建议最稳妥的做法是把所有时间维度上的dp[t][n-1]全部算完最后统一取最小值整个过程不做提前终止。只有在极大规模数据下为了效率尝试剪枝才可以在某条路径的费用已经超过当前已知答案时跳过如下面这个判断if (dp[t][u] ans) continue;这个剪枝不会影响正确性因为费用只会增加不会减少但ans仍然要放在最后统一更新。4.3 为什么不能用 Dijkstra 直接改一改这个问题几乎每一版题解下面都有人问。Dijkstra 的堆优化写法确实可以处理一些路径长度和花费的双限制问题但核心前提是贪心选择不会导致漏解。在这道题里费用最优和时间最优不一定落在同一条路径上某一时刻你从堆里弹出的节点可能是当前路径费用最小的但这不代表从它往下走能拼出全局费用最小且时间合法的路径。另一个更符合 DP 直觉的比喻是你手里有两张表一张记录时间有多短一张记录费用有多低两者没法合并成一个排序维度。除非你引入启发式函数比如用A*做带剪枝的搜索那又另当别论。4.4 踩过的坑双向边、重复到达同一城市、大时间上限我实际踩过一次反向边漏加的错误。排查方法很简单自己构造一个只有两个城市的用例maxTime 5道路0 - 1耗时1。如果建图只建了0 - 1那dp在正向转移时没问题但如果你加一条道路1 - 0然后想规划从0走到1再绕回0再走到1的路线那么反向边缺失就会直接导致dp无法更新。这类问题调试起来很容易一眼瞟过所以我习惯把双向边这一句注释直接写在建图旁边。另外还有一个细节由于图中有环同一城市可能在不同时间点被多次到达这是合法的。比如dp[3][1] 5dp[6][1] 8两条路径都能走到城市 1只是耗时不同费用也不同。DP 不能简单地认为既然城市 1 已经被访问过就可以不用再访问第二次——在这个题的模型里访问时间不同后面路径的剩余时间预算就不同。这也是为什么有些人用 visited 数组标记剪枝会出问题的原因。只有当某个状态既时间更大又费用更大即严格被其他状态支配时才可以安全剪枝但这种检查比较麻烦比赛中一般不值得做。最后说一个关于语言细节的事Python 写dp[mx 1][n]这种大列表如果数据规模大一点很容易踩到运行时间红线而 C 的vectorvectorint在同样规模下通常更稳。如果习惯用 Python 刷题可以尝试把二维数组换成一维和二维混合的字典或者改用列表推导式并尽量少在循环里做嵌套属性访问。这道题我在 C 版本上运行耗时约几十毫秒在 Python 下需要稍微注意常数优化。5. 从这道题延伸开去一类时间 / 步数 / 预算限制题的通用解这种限制一个维度的最大值求另一个维度的最小值的模型在 LeetCode 上不是孤例。比如有一道很经典的题是求最多经停 K 站的最便宜航班用的状态就是dp[k][v]表示经过不超过k次转移到达城市v的最小费用其结构和本题几乎一模一样只是把时间维度换成了步数维度。再比如一些背包类问题把花费的硬币数作为状态维度把购买到的价值作为优化目标也是同一个套路。所以当你再看到这类题时可以快速做一个条件判断是否有一个维度是可枚举且范围可接受的整数时间、步数、剩余预算、已选数量等。如果答案是可以那么二维 DP 往往就是最简单直接的解法。状态定义里放一个约束维度转移时另一个约束变成条件判断优化目标作为 DP 的值这种思路几乎可以套用到所有双限制求最优的问题上。我做这类题时还有一个习惯先不急着写代码先在纸上画一个表格横轴是时间纵轴是城市然后手动填几行。一旦你在表格里填对了起点那一格后面的所有转移都会顺理成章地落在表格里整个递推过程就一目了然了。这个方法也推荐给你比你直接盯着代码想边界条件要高效得多。最后分享一个解题顺序先看数据范围确认maxTime * n能否承受再看路径定义有没有双向边最后确认起点终点的费用是否计入。这三点都检查完这道题的正确率基本上就已经能保证了。