教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文是「算法通关手册」AlgoNote中 0656. 成本最小路径 的完整技术解析。该题是 LeetCode 上一道结合「数组」与「动态规划」的困难题核心难点有两个一是从起点到终点的最小成本路径二是在存在多条等成本路径时如何返回字典序最小的那条。读完本文你将掌握反向动态规划的推导方法、通过维护next前驱数组完成路径重构的技巧以及在成本相同情况下保证字典序最小的贪心策略并理解为什么正向 DP 无法满足字典序要求。题目背景与题目链接标签数组、动态规划难度困难题目链接0656. 成本最小路径 - 力扣本题收录于「算法通关手册」的 0600-0699 章节索引并在 题解总览列表 中登记为「数组、动态规划」标签下的困难题。从该题的典型性来看它非常适合作为「动态规划 路径重构」的进阶训练题目。题目大意给定一个整数数组coins下标从1开始长度为n以及一个整数maxJump。你可以跳到数组coins的任意下标i满足coins[i] ! -1访问下标i时需要支付coins[i]。此外如果你当前位于下标i你只能跳到下标i k满足i k n其中k是范围[1, maxJump]内的一个值。初始时你位于下标1coins[1]不是-1。要求找到一条到达下标n的成本最小路径返回一个整数数组包含你访问的下标顺序。如果存在多条成本相同的路径返回字典序最小的路径如果无法达到下标n返回一个空数组。字典序定义路径p1 [Pa1, Pa2, ..., Pax]的长度为x路径p2 [Pb1, Pb2, ..., Pby]的长度为y如果在两条路径的第一个不同的下标j处Paj Pbj则p1在字典序上小于p2如果不存在这样的j则较短的路径字典序较小。数据范围说明1 coins.length 10^3-1 coins[i] 10^3coins[1] ! -11 maxJump 10^3示例示例 1输入coins [1,2,4,-1,2], maxJump 2 输出[1,3,5]示例 2输入coins [1,2,4,-1,2], maxJump 1 输出[]示例 2 中maxJump 1意味着每次只能跳一步而下标4的coins[4] -1不可访问因此无法到达下标5返回空数组。解题思路反向动态规划本题要求在「最小成本」与「字典序最小」两个维度上同时满足要求。我们可以使用反向动态规划来解决即从终点往前推定义dp[i]表示从位置i到达终点的最小成本。为什么使用反向 DP当成本相同时我们需要选择字典序最小的路径从后往前 DP 时如果成本相同选择索引较小的下一个节点这样可以保证字典序最小如果从前往后 DP即使每一步选择索引较小的前驱节点也无法保证整个路径的字典序最小——因为前面的节点一旦选定后面节点的取舍空间已被压缩局部贪心无法等价于全局字典序最优。这也与「算法通关手册」动态规划基础篇中关于「无后效性」的论述一脉相承反向递推保证了状态只依赖「已确定的后缀最优解」从而在确定当前决策时不受前方路径选择的影响。可参考 动态规划基础 中关于最优子结构与无后效性的说明。算法步骤初始化dp数组dp[n-1] coins[n-1]终点位置的成本从后往前遍历每个位置i枚举所有可能的下一个位置j满足i j i maxJump且j n更新dp[i]使用next[i]数组记录从位置i出发的下一个节点。如果成本相同选择索引较小的下一个节点保证字典序最小从起点开始沿着next数组构造路径。注意如果某个位置的coins[i] -1则该位置不可达需要直接跳过。思路 1完整代码class Solution: def cheapestJump(self, coins: List[int], maxJump: int) - List[int]: n len(coins) # 如果起点或终点不可达返回空数组 if coins[0] -1 or coins[n - 1] -1: return [] # dp[i] 表示从位置 i 到达终点的最小成本 dp [float(inf)] * n dp[n - 1] coins[n - 1] # next_node[i] 表示从位置 i 出发的下一个节点用于构造字典序最小的路径 next_node [-1] * n # 从后往前进行动态规划 for i in range(n - 2, -1, -1): if coins[i] -1: continue # 枚举所有可能的下一个位置 for j in range(i 1, min(i maxJump 1, n)): if coins[j] -1: continue # 如果从 j 无法到达终点跳过 if dp[j] float(inf): continue cost coins[i] dp[j] # 更新最小成本和下一个节点 if cost dp[i]: dp[i] cost next_node[i] j elif cost dp[i] and (next_node[i] -1 or j next_node[i]): # 成本相同选择索引较小的下一个节点保证字典序最小 next_node[i] j # 如果无法从起点到达终点 if dp[0] float(inf): return [] # 从起点开始沿着 next_node 数组构造路径 path [] i 0 # 沿着 next_node 数组遍历直到到达终点 while i n and next_node[i] 0: path.append(i 1) # 题目中位置从 1 开始 i next_node[i] # 检查是否成功到达终点 if i n - 1 and coins[i] 0: path.append(n) else: return [] return path代码关键点逐行解读初始化dp[n-1] coins[n-1]给出终点的边界状态其余位置初始化为float(inf)表示「不可达」这与 DP 基础篇中「先求解子问题、再逐步递推」的思想一致枚举跳转范围range(i 1, min(i maxJump 1, n))精确对应题目约束k ∈ [1, maxJump]且i k n成本平局处理elif cost dp[i] and (next_node[i] -1 or j next_node[i])是关键语句——当两种方案成本相同且j的索引更小时替换next_node[i]。由于j从小到大枚举这里也可直接写作「成本相等时取更小的j」路径构造path.append(i 1)将 0 基索引转换为题目要求的 1 基下标最后单独追加终点下标n兜底校验若沿next_node走到尽头仍未到达n-1说明存在断链如终点为-1或路径中断此时返回空数组。为什么不能用正向 DP 保证字典序最小正向 DP 的经典写法是dp[i]表示「从起点到位置i的最小成本」转移时dp[i] coins[i] min(dp[i-k])。但正向 DP 在记录路径时只能记录「到达i的前驱节点」。若存在两条成本相同的路径抵达不同前驱正向贪心地选择较小前驱表面上满足局部字典序但后续终点的选取会被锁定最终可能导致整条路径在「首个不同下标处」字典序更大。反向 DP 则不同它在处理位置i时dp[j]已经是「从j到终点的最优解」且j是i之后的节点。此时选择索引更小的j等价于在当前位置直接决定了路径上「第一个不同的下标」因此可以保证整条路径字典序最小。这正是本题选择反向 DP 的深层原因。复杂度分析时间复杂度O(n × maxJump)其中n是数组的长度。外层循环遍历n个位置内层循环最多枚举maxJump个后继位置。空间复杂度O(n)。需要使用两个长度为n的数组存储动态规划的状态dp和下一个节点信息next_node。在n 10^3、maxJump 10^3的数据范围内最坏情况下的操作数约为10^6量级完全在时间限制内可接受。举一反三与其他动态规划题的联系本题属于「图上的最短路径问题 字典序最小」的复合题型与仓库中其他动态规划题目可以串联学习0064. 最小路径和同样是「路径 最小成本」问题但其状态定义是正向的dp[i][j]从左上角到达(i,j)的最小路径和因为网格问题中的移动方向天然无后效正向定义即可本题的跳转步长可变且需要输出路径本身因此反向定义更为合适0700 系列与区间 DP / 树形 DP路径重构维护前驱数组是输出型 DP 题的通用技法掌握后可以迁移到「最长递增子序列的输出」「拓扑排序路径记录」等场景。建议配合 LeetCode 刷题指南 中「执行代码 → 提交 → 分析复杂度」的完整流程将本题代码在本地或评测平台反复验证示例数据与边界用例如coins全为正数、存在多个-1、maxJump 1等。小结成本最小路径 是一道非常经典的「反向动态规划 字典序最小」训练题。其核心收获有三点状态设计dp[i]定义为「从i到终点的最小成本」从终点向起点反向递推平局策略成本相同时选择索引更小的下一个节点即可保证整条路径字典序最小路径重构通过next_node前驱数组在 DP 完成后自起点一路追踪到终点将最优解输出为具体路径。掌握了反向 DP 与字典序平局处理这两个要点这一思路可以平滑迁移到其他「输出最优方案」类的动态规划题目中。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0499 迷宫 III —— Dijkstra 优先队列求解字典序最小的最短路径AlgoNote 算法通关手册LeetCode 0499 迷宫 III —— Dijkstra 优先队列求解字典序最小的最短路径 本文是「 算法通关手册 ht教程文档知识库LeetCode 题解Minimum Dropping Path Sum —— 相邻行不同列的路径和最小化动态规划 滚动数组LeetCode 题解Minimum Dropping Path Sum —— 相邻行不同列的路径和最小化动态规划 滚动数组 导读 Minimum D文档教程知识库LeetCode 64. Minimum Path Sum 题解Go 实现的最小路径和动态规划原地 DP 与二维 DP 双解法LeetCode 64. Minimum Path Sum 题解Go 实现的最小路径和动态规划原地 DP 与二维 DP 双解法 本篇围绕 LeetCode示例工程上一篇CANN ops-math Lerp 算子全解析从 aclnnLerp 接口到 Ascend 内核实现下一篇如何彻底去除Unity游戏马赛克7个免费去马赛克插件完整配置指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考