LeetCode 1928. 规定时间内到达终点的最小花费 | 动态规划状态递推 超详细题解 题目详解 最优DP解法 代码逐行解析题目难度中等 核心考点动态规划、状态压缩、带约束的最短路径、图论递推适用人群算法进阶、DP专项练习、图论入门一、题目描述一个国家有n个城市城市编号为0到n - 1题目保证所有城市都由双向道路连接在一起。道路由二维整数数组edges表示其中edges[i] [xi, yi, timei]表示城市xi和yi之间有一条双向道路耗费时间为timei分钟。两个城市之间可能会有多条耗费时间不同的道路不会有自环道路。每次经过一个城市时需要支付通行费通行费用长度为n的数组passingFees表示passingFees[j]为经过城市j的费用。初始位置城市0目标在maxTime分钟以内包含maxTime到达城市n-1。总费用规则经过的所有城市通行费之和包含起点0和终点n-1。请返回完成旅行的最小费用如果无法在规定时间内到达终点返回-1。数据范围1 ≤ maxTime ≤ 1000n passingFees.length2 ≤ n ≤ 1000n - 1 ≤ edges.length ≤ 10001 ≤ timei ≤ 10001 ≤ passingFees[j] ≤ 1000图为连通无向图可存在重边无自环二、示例演示与解析示例 1输入maxTime 30, edges [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees [5,1,2,20,20,3]输出11解释最优路径为0 → 1 → 2 → 5总耗时30分钟刚好达标总费用5(0)1(1)2(2)3(5)11。示例 2输入maxTime 29, edges 同示例1, passingFees 同示例1输出48解释原路径耗时30分钟超出限制更换路径为0 → 3 → 4 → 5总耗时26分钟总费用52020348。示例 3输入maxTime 25, edges 同示例1, passingFees 同示例1输出-1解释所有可行路径耗时均超过25分钟无法到达终点返回-1。三、解题思路分析题型定位本题属于带双重约束的路径优化问题以时间为硬性上限约束以费用为最小化优化目标本质是图论中的最短路径变种区别于普通最短路径本题优先满足时间限制再求费用最小。解法选型动态规划DP结合数据范围特点maxTime ≤ 1000、n ≤ 1000采用时间维度城市维度的二维动态规划是最直观、易实现、无超时风险的解法无需复杂堆优化逻辑清晰不易出错。核心状态定义dp[t][v]表示恰好花费t分钟到达城市v时所需支付的最小总通行费。状态初始化初始在城市0耗时0分钟需支付起点费用因此dp[0][0] passingFees[0]其余状态初始化为无穷大表示初始不可达。状态转移方程图为无向图每条道路可双向通行对每条边(u, v, w)若当前耗时t从u走到v耗时变为tw且不超过maxTime则dp[tw][v] min(dp[tw][v], dp[t][u] passingFees[v])若当前耗时t从v走到u耗时变为tw且不超过maxTime则dp[tw][u] min(dp[tw][u], dp[t][v] passingFees[u])结果取值遍历所有0 ≤ t ≤ maxTime取dp[t][n-1]的最小值即为答案若最小值仍为无穷大返回-1。思路优势贴合数据范围maxTime仅1000二维DP空间完全可控递推逻辑简单按时间从小到大遍历无后效性无需处理环路重复计算覆盖所有场景包含重边、多路径、时间临界、不可达等边界情况四、完整代码实现严格遵循指定代码格式添加详细注释优化无穷大取值适配Python运行效率直接提交可ACfromtypingimportListclassSolution:defminCost(self,maxTime:int,edges:List[List[int]],passingFees:List[int])-int:# 城市数量nlen(passingFees)# 定义无穷大取值大于最大可能费用1000个城市*1000费用1e6INFfloat(inf)# dp[t][v]耗时t分钟到达城市v的最小费用dp[[INF]*nfor_inrange(maxTime1)]# 初始状态0分钟在城市0支付起点费用dp[0][0]passingFees[0]# 按时间从小到大递推遍历所有可行时间fortinrange(maxTime):# 遍历所有双向边进行状态转移foru,v,time_costinedges:# 新时间不超过maxTime才进行转移new_timettime_costifnew_timemaxTime:continue# 从u到v的转移ifdp[t][u]!INF:dp[new_time][v]min(dp[new_time][v],dp[t][u]passingFees[v])# 从v到u的转移无向图双向通行ifdp[t][v]!INF:dp[new_time][u]min(dp[new_time][u],dp[t][v]passingFees[u])# 取所有时间内到达终点的最小费用min_total_costmin(dp[t][n-1]fortinrange(maxTime1))# 不可达返回-1否则返回最小费用returnmin_total_costifmin_total_cost!INFelse-1五、代码逐行深度解析1. 初始化与状态定义nlen(passingFees)INFfloat(inf)dp[[INF]*nfor_inrange(maxTime1)]dp[0][0]passingFees[0]无穷大取值选用float(inf)大于最大可能总费用1000×100010⁶避免溢出二维dp数组维度为(maxTime1) × n覆盖0到maxTime所有时间点初始全为不可达起点状态必须初始化0分钟在城市0需支付城市0的通行费。2. 时间递推与状态转移fortinrange(maxTime):foru,v,time_costinedges:new_timettime_costifnew_timemaxTime:continueifdp[t][u]!INF:dp[new_time][v]min(dp[new_time][v],dp[t][u]passingFees[v])ifdp[t][v]!INF:dp[new_time][u]min(dp[new_time][u],dp[t][v]passingFees[u])按时间从小到大遍历保证后续时间状态由前面状态推导而来满足DP无后效性无向图必须做双向转移每条边兼顾u→v和v→u两种走法提前判断新时间是否超出限制跳过无效转移减少不必要计算仅当前状态可达非无穷大时才进行后续转移避免无效赋值。3. 结果计算与边界处理min_total_costmin(dp[t][n-1]fortinrange(maxTime1))returnmin_total_costifmin_total_cost!INFelse-1遍历所有≤maxTime的时间点取终点最小费用覆盖“耗时更少、费用更低”的所有路径若终点所有时间状态均不可达返回-1符合题目要求。六、复杂度分析时间复杂度O(maxTime × E)其中E为边的数量外层循环maxTime次最多1000次内层循环遍历所有边最多1000条总运算量1000×10001e6完全在Python时间限制内运行高效无压力。空间复杂度O(maxTime × n)二维dp数组占用空间1000×10001e6Python可轻松承载无需空间优化若需优化空间可改用滚动数组将空间降至O(n)本题无需额外优化。七、易错点总结❌ 忘记包含起点/终点费用必须计入所有经过城市初始状态必须赋值passingFees[0]❌ 无向图只做单向转移遗漏反向路径导致部分可行路径未被计算❌ 时间超出maxTime仍转移违反题目时间限制生成无效状态❌ 无穷大取值过小导致状态溢出误判为可达❌ 只取maxTime时刻的结果忽略耗时更少、费用更低的可行路径。八、拓展思路进阶优化滚动数组优化空间由于状态仅依赖上一时刻可用两个一维数组交替更新空间复杂度降至O(n)Dijkstra算法变种将费用、时间、城市作为状态用小根堆优先弹出费用最小的状态剪枝时间超出限制的路径适合更大数据范围剪枝优化同一城市、同一时间若已有更小费用直接跳过更大费用的状态转移。九、总结本题是动态规划在图论路径问题中的经典应用核心突破口是利用时间范围小的特点以时间为维度构建DP状态兼顾约束条件与优化目标。解法实现简单、逻辑直观完美适配题目数据范围同时覆盖了无向图、重边、边界不可达等各类场景。同类带约束的最短路径问题均可参考此思路以约束条件为DP维度以优化目标为状态值按顺序递推即可高效求解。原创题解码字不易欢迎点赞、收藏⭐、关注后续持续更新LeetCode高频中等题的详细解法与思路拆解
LeetCode 1928. 规定时间内到达终点的最小花费 _ 动态规划+状态递推 超详细题解
发布时间：2026/5/20 3:10:23
LeetCode 1928. 规定时间内到达终点的最小花费 | 动态规划状态递推 超详细题解 题目详解 最优DP解法 代码逐行解析题目难度中等 核心考点动态规划、状态压缩、带约束的最短路径、图论递推适用人群算法进阶、DP专项练习、图论入门一、题目描述一个国家有n个城市城市编号为0到n - 1题目保证所有城市都由双向道路连接在一起。道路由二维整数数组edges表示其中edges[i] [xi, yi, timei]表示城市xi和yi之间有一条双向道路耗费时间为timei分钟。两个城市之间可能会有多条耗费时间不同的道路不会有自环道路。每次经过一个城市时需要支付通行费通行费用长度为n的数组passingFees表示passingFees[j]为经过城市j的费用。初始位置城市0目标在maxTime分钟以内包含maxTime到达城市n-1。总费用规则经过的所有城市通行费之和包含起点0和终点n-1。请返回完成旅行的最小费用如果无法在规定时间内到达终点返回-1。数据范围1 ≤ maxTime ≤ 1000n passingFees.length2 ≤ n ≤ 1000n - 1 ≤ edges.length ≤ 10001 ≤ timei ≤ 10001 ≤ passingFees[j] ≤ 1000图为连通无向图可存在重边无自环二、示例演示与解析示例 1输入maxTime 30, edges [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees [5,1,2,20,20,3]输出11解释最优路径为0 → 1 → 2 → 5总耗时30分钟刚好达标总费用5(0)1(1)2(2)3(5)11。示例 2输入maxTime 29, edges 同示例1, passingFees 同示例1输出48解释原路径耗时30分钟超出限制更换路径为0 → 3 → 4 → 5总耗时26分钟总费用52020348。示例 3输入maxTime 25, edges 同示例1, passingFees 同示例1输出-1解释所有可行路径耗时均超过25分钟无法到达终点返回-1。三、解题思路分析题型定位本题属于带双重约束的路径优化问题以时间为硬性上限约束以费用为最小化优化目标本质是图论中的最短路径变种区别于普通最短路径本题优先满足时间限制再求费用最小。解法选型动态规划DP结合数据范围特点maxTime ≤ 1000、n ≤ 1000采用时间维度城市维度的二维动态规划是最直观、易实现、无超时风险的解法无需复杂堆优化逻辑清晰不易出错。核心状态定义dp[t][v]表示恰好花费t分钟到达城市v时所需支付的最小总通行费。状态初始化初始在城市0耗时0分钟需支付起点费用因此dp[0][0] passingFees[0]其余状态初始化为无穷大表示初始不可达。状态转移方程图为无向图每条道路可双向通行对每条边(u, v, w)若当前耗时t从u走到v耗时变为tw且不超过maxTime则dp[tw][v] min(dp[tw][v], dp[t][u] passingFees[v])若当前耗时t从v走到u耗时变为tw且不超过maxTime则dp[tw][u] min(dp[tw][u], dp[t][v] passingFees[u])结果取值遍历所有0 ≤ t ≤ maxTime取dp[t][n-1]的最小值即为答案若最小值仍为无穷大返回-1。思路优势贴合数据范围maxTime仅1000二维DP空间完全可控递推逻辑简单按时间从小到大遍历无后效性无需处理环路重复计算覆盖所有场景包含重边、多路径、时间临界、不可达等边界情况四、完整代码实现严格遵循指定代码格式添加详细注释优化无穷大取值适配Python运行效率直接提交可ACfromtypingimportListclassSolution:defminCost(self,maxTime:int,edges:List[List[int]],passingFees:List[int])-int:# 城市数量nlen(passingFees)# 定义无穷大取值大于最大可能费用1000个城市*1000费用1e6INFfloat(inf)# dp[t][v]耗时t分钟到达城市v的最小费用dp[[INF]*nfor_inrange(maxTime1)]# 初始状态0分钟在城市0支付起点费用dp[0][0]passingFees[0]# 按时间从小到大递推遍历所有可行时间fortinrange(maxTime):# 遍历所有双向边进行状态转移foru,v,time_costinedges:# 新时间不超过maxTime才进行转移new_timettime_costifnew_timemaxTime:continue# 从u到v的转移ifdp[t][u]!INF:dp[new_time][v]min(dp[new_time][v],dp[t][u]passingFees[v])# 从v到u的转移无向图双向通行ifdp[t][v]!INF:dp[new_time][u]min(dp[new_time][u],dp[t][v]passingFees[u])# 取所有时间内到达终点的最小费用min_total_costmin(dp[t][n-1]fortinrange(maxTime1))# 不可达返回-1否则返回最小费用returnmin_total_costifmin_total_cost!INFelse-1五、代码逐行深度解析1. 初始化与状态定义nlen(passingFees)INFfloat(inf)dp[[INF]*nfor_inrange(maxTime1)]dp[0][0]passingFees[0]无穷大取值选用float(inf)大于最大可能总费用1000×100010⁶避免溢出二维dp数组维度为(maxTime1) × n覆盖0到maxTime所有时间点初始全为不可达起点状态必须初始化0分钟在城市0需支付城市0的通行费。2. 时间递推与状态转移fortinrange(maxTime):foru,v,time_costinedges:new_timettime_costifnew_timemaxTime:continueifdp[t][u]!INF:dp[new_time][v]min(dp[new_time][v],dp[t][u]passingFees[v])ifdp[t][v]!INF:dp[new_time][u]min(dp[new_time][u],dp[t][v]passingFees[u])按时间从小到大遍历保证后续时间状态由前面状态推导而来满足DP无后效性无向图必须做双向转移每条边兼顾u→v和v→u两种走法提前判断新时间是否超出限制跳过无效转移减少不必要计算仅当前状态可达非无穷大时才进行后续转移避免无效赋值。3. 结果计算与边界处理min_total_costmin(dp[t][n-1]fortinrange(maxTime1))returnmin_total_costifmin_total_cost!INFelse-1遍历所有≤maxTime的时间点取终点最小费用覆盖“耗时更少、费用更低”的所有路径若终点所有时间状态均不可达返回-1符合题目要求。六、复杂度分析时间复杂度O(maxTime × E)其中E为边的数量外层循环maxTime次最多1000次内层循环遍历所有边最多1000条总运算量1000×10001e6完全在Python时间限制内运行高效无压力。空间复杂度O(maxTime × n)二维dp数组占用空间1000×10001e6Python可轻松承载无需空间优化若需优化空间可改用滚动数组将空间降至O(n)本题无需额外优化。七、易错点总结❌ 忘记包含起点/终点费用必须计入所有经过城市初始状态必须赋值passingFees[0]❌ 无向图只做单向转移遗漏反向路径导致部分可行路径未被计算❌ 时间超出maxTime仍转移违反题目时间限制生成无效状态❌ 无穷大取值过小导致状态溢出误判为可达❌ 只取maxTime时刻的结果忽略耗时更少、费用更低的可行路径。八、拓展思路进阶优化滚动数组优化空间由于状态仅依赖上一时刻可用两个一维数组交替更新空间复杂度降至O(n)Dijkstra算法变种将费用、时间、城市作为状态用小根堆优先弹出费用最小的状态剪枝时间超出限制的路径适合更大数据范围剪枝优化同一城市、同一时间若已有更小费用直接跳过更大费用的状态转移。九、总结本题是动态规划在图论路径问题中的经典应用核心突破口是利用时间范围小的特点以时间为维度构建DP状态兼顾约束条件与优化目标。解法实现简单、逻辑直观完美适配题目数据范围同时覆盖了无向图、重边、边界不可达等各类场景。同类带约束的最短路径问题均可参考此思路以约束条件为DP维度以优化目标为状态值按顺序递推即可高效求解。原创题解码字不易欢迎点赞、收藏⭐、关注后续持续更新LeetCode高频中等题的详细解法与思路拆解
