企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

本文是「算法通关手册」（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]内的一个值。

初始时你位于下标1（coins[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^3
• coins[1] != -1
• 1 <= 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，即使每一步选择索引较小的前驱节点，也无法保证整个路径的字典序最小——因为前面的节点一旦选定，后面节点的取舍空间已被压缩，局部贪心无法等价于全局字典序最优。

这也与「算法通关手册」动态规划基础篇中关于「无后效性」的论述一脉相承：反向递推保证了状态只依赖「已确定的后缀最优解」，从而在确定当前决策时不受前方路径选择的影响。可参考 动态规划基础 中关于最优子结构与无后效性的说明。

算法步骤

1. 初始化dp数组，dp[n-1] = coins[n-1]（终点位置的成本）；
2. 从后往前遍历每个位置i，枚举所有可能的下一个位置j（满足i < j <= i + maxJump且j < n），更新dp[i]；
3. 使用next[i]数组记录从位置i出发的下一个节点。如果成本相同，选择索引较小的下一个节点（保证字典序最小）；
4. 从起点开始，沿着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等）。

小结

656. 成本最小路径 是一道非常经典的「反向动态规划 + 字典序最小」训练题。其核心收获有三点：

657. 状态设计：dp[i]定义为「从i到终点的最小成本」，从终点向起点反向递推；

658. 平局策略：成本相同时，选择索引更小的下一个节点，即可保证整条路径字典序最小；

659. 路径重构：通过next_node前驱数组在 DP 完成后自起点一路追踪到终点，将最优解输出为具体路径。

掌握了反向 DP 与字典序平局处理这两个要点，这一思路可以平滑迁移到其他「输出最优方案」类的动态规划题目中。

• 教程
• 文档
• 知识库