LeetCode 656. 成本最小路径
目录
题目描述
题意分析
要什么：从下标 0 出发跳到下标
n-1，每次最多向右跳B步，落在下标i要付出A[i]的代价，A[i] == -1表示该位置不可落脚。求总代价最小的路径本身（用 1-based 下标序列表示），无法抵达返回空数组。若最小代价有多条路径达成，返回字典序最小的那条。
约束透露的信号：题目要的不是最小值而是路径，说明除了代价表还必须保留「下一步跳到哪」的决策记录，否则算完只有一个数字无法还原方案。「字典序最小」这个附加要求进一步说明：转移时不能随便挑一个最优前驱，必须在代价相等时按下标做确定性的取舍。每步跳跃范围是B，转移的分支数就是B，所以 $O(nB)$ 的朴素 DP 就是预期解。
边界：终点若是-1则直接无解；起点若是-1同样无解（代码中体现为dp[0]仍为无穷）；跳跃上界要与n-1取较小值防越界；代价累加在最坏情况下可能超出 32 位，用 64 位更稳；无解时返回的是空数组而不是null或[-1]。
解法：从后往前 DP + next 恢复路径
核心思路
暴力是从起点做深度优先搜索，枚举每一步跳 1 到
B格，记录走过的路径和累计代价，最后在所有可行路径里取最优。分支数 $B^n$，指数爆炸。
瓶颈在于同一个下标会被无数条不同前缀重复展开，而「从下标i走到终点的最优代价」其实与「怎么走到i的」完全无关——这正是最优子结构，也是可以做记忆化 / DP 的信号。
于是状态定义为：dp[i]= 从下标i出发、最终抵达n-1所需的最小总代价（含A[i]自身，不可达记为无穷大）；配套的决策记录next[i]= 在取得dp[i]的最优方案中，从i迈出的第一步落在哪个下标（没有则为 -1）。
转移是dp[i] = A[i] + min{ dp[j] }，其中j取遍i+1 .. min(n-1, i+B)且dp[j]有限。边界是dp[n-1] = A[n-1]。因为dp[i]依赖的全是更大的下标，所以必须从后往前推。
为什么这个「从后往前」的定义比「从前往后」更好？因为答案要的是从 0 出发的路径，next指针天然形成一条从 0 开始的单链，顺着走一遍就是答案，不需要反转。
字典序最小怎么保证？路径以 1-based 下标序列比较，两条同代价路径从i出发，第一处差异就是第一跳的落点，落点下标越小字典序越小。所以在dp[j]相等时必须选最小的j。代码里j从小到大枚举、只在严格更小时才更新best，因此第一个取到最小值的j会被保留下来，恰好就是最小下标；再配合每个next[j]自身也是按同样规则选出的，整条链递归地保持字典序最小。
解题步骤
- 若
A[n-1] == -1直接返回空数组。为什么要提前拦：终点不可落脚意味着任何路径都不合法，而后续的dp[n-1] = A[n-1]会把 -1 当成一个「代价为 -1」的合法边界，污染整张表。- 把
dp全部初始化为一个足够大的哨兵值、next全部初始化为 -1，然后设dp[n-1] = A[n-1]。为什么哨兵要用 64 位的大数而不是Integer.MAX_VALUE：转移里有best + A[i]的加法，用 32 位最大值会溢出成负数，反而被误判为「更优」；用1e18级别的long既不会溢出也远大于任何真实代价。- 从
i = n-2倒序遍历到 0，遇到A[i] == -1直接跳过。为什么倒序：dp[i]依赖dp[i+1 .. i+B]，只有先算完右边才能算左边；正序会读到尚未计算的哨兵值，全表作废。为什么跳过而不是设无穷：dp[i]初值本就是无穷，跳过等价于宣告该位置不可落脚，语义一致。- 内层在
j = i+1 .. min(n-1, i+B)中找最小的dp[j]，跳过dp[j]仍为哨兵的下标。为什么必须跳过不可达的j：哨兵值参与best + A[i]会算出一个巨大但有限的数，让本该不可达的位置伪装成可达。为什么上界要和n-1取小：i + B可能越过数组末尾，直接索引会越界。- 找到
bestJ后写入dp[i] = best + A[i]、next[i] = bestJ；没找到则保持无穷、next保持 -1。为什么next的默认值必须是 -1：它同时充当「链表终止标记」，路径恢复时靠cur != -1退出循环，dp[n-1]对应的next[n-1]天然是 -1，正好在终点停下。- 若
dp[0]仍是哨兵，说明起点不可达终点，返回空数组。- 否则从
cur = 0沿next链一路走，每步把cur + 1追加进结果。为什么要 +1：题目要求 1-based 下标。- 以
A = [1, 2, 4, -1, 2]、B = 2走一遍。n = 5，终点A[4] = 2合法，故dp[4] = 2、其余为无穷、next全 -1。i = 3：A[3] == -1，跳过，dp[3]保持无穷。i = 2：上界min(4, 4) = 4，枚举j = 3（dp[3]无穷，跳过）、j = 4（dp[4] = 2有限，best = 2、bestJ = 4），于是dp[2] = 2 + 4 = 6、next[2] = 4。i = 1：上界min(4, 3) = 3，枚举j = 2（dp[2] = 6，best = 6、bestJ = 2）、j = 3（无穷，跳过），于是dp[1] = 6 + 2 = 8、next[1] = 2。i = 0：上界min(4, 2) = 2，枚举j = 1（dp[1] = 8，先记best = 8、bestJ = 1）、j = 2（dp[2] = 6 < 8，更新best = 6、bestJ = 2），于是dp[0] = 6 + 1 = 7、next[0] = 2。dp[0] = 7有限，从cur = 0恢复路径：记录 1，跳到next[0] = 2；记录 3，跳到next[2] = 4；记录 5，跳到next[4] = -1结束。返回[1, 3, 5]，总代价1 + 4 + 2 = 7，与dp[0]吻合，且中途绕开了不可落脚的下标 3。
代码实现
// 核心实现：从后往前 DP + next 恢复路径，维护必要状态并避免重复处理。
class Solution {
public List<Integer> cheapestJump(int[] A, int B) {
int n = A.length;
if (A[n - 1] == -1) {
return new ArrayList<>();
}
long INF = (long) 1e18;
long[] dp = new long[n];
int[] next = new int[n];
Arrays.fill(dp, INF);
Arrays.fill(next, -1);
dp[n - 1] = A[n - 1];
for (int i = n - 2; i >= 0; i--) {
if (A[i] == -1) {
continue;
}
long best = INF;
int bestJ = -1;
int upper = Math.min(n - 1, i + B);
for (int j = i + 1; j <= upper; j++) {
if (dp[j] == INF) {
continue;
}
if (dp[j] < best || (dp[j] == best && j < bestJ)) {
best = dp[j];
bestJ = j;
}
}
if (bestJ != -1) {
dp[i] = best + A[i];
next[i] = bestJ;
}
}
if (dp[0] == INF) {
return new ArrayList<>();
}
List<Integer> path = new ArrayList<>();
int cur = 0;
while (cur != -1) {
path.add(cur + 1);
cur = next[cur];
}
return path;
}
}
// 核心实现：从后往前 DP + next 恢复路径，维护必要状态并避免重复处理。
func cheapestJump(A []int, B int) []int {
n := len(A)
if A[n-1] == -1 {
return []int{}
}
const INF int64 = 1<<62
dp := make([]int64, n)
next := make([]int, n)
for i := range dp {
dp[i] = INF
next[i] = -1
}
dp[n-1] = int64(A[n-1])
for i := n - 2; i >= 0; i-- {
if A[i] == -1 {
continue
}
best := INF
bestJ := -1
upper := i + B
if upper > n-1 {
upper = n - 1
}
for j := i + 1; j <= upper; j++ {
if dp[j] == INF {
continue
}
if dp[j] < best || (dp[j] == best && j < bestJ) {
best = dp[j]
bestJ = j
}
}
if bestJ != -1 {
dp[i] = best + int64(A[i])
next[i] = bestJ
}
}
if dp[0] == INF {
return []int{}
}
path := make([]int, 0)
cur := 0
for cur != -1 {
path = append(path, cur+1)
cur = next[cur]
}
return path
}
复杂度分析
- 时间复杂度：$O(nB)$。凭什么：外层遍历
n个下标，内层最多枚举B个跳跃目标，每次做常数比较；末尾的路径恢复不超过n步，量级更小。- 空间复杂度：$O(n)$。凭什么：
dp与next各占一条长度n的数组，答案路径最长也是n；没有二维表，也没有递归栈。
关键点总结
- 要输出方案就必须存决策：DP 表只回答「最优值是多少」，想回答「怎么取到的」就得同步维护一个
next（或from）指针数组。这是路径 DP 与普通 DP 的分水岭，也是本题被标为困难的主要原因。- 状态方向由输出需求决定：本题定义成「从
i到终点」而不是「从起点到i」，就是为了让next链从 0 开始顺着走，省掉反转。设计状态时先想清楚最后要怎么把答案读出来。- 字典序最小 = 在每个决策点上对并列项取最小下标，并且这个规则要在链条的每一环都成立。实现上只要「升序枚举 + 严格小于才更新」即可自然满足，不必额外写比较逻辑。
- 哨兵值的选取是有讲究的：既要大到不可能被误认为最优，又要小到参与加法不会溢出。用 32 位最大值做无穷大再做加法，是这类题最经典的翻车方式。
- 面试视角：先说状态定义和转移，再单独强调「不可达用哨兵、哨兵不参与转移」和「并列取小下标保证字典序」两个细节，最后演示路径恢复。被追问优化时可以提「内层的区间最小值可以用单调队列压到 $O(n)$」，但要说明当前数据规模下 $O(nB)$ 已足够。
易错点总结
- 错误写法：漏掉
A[n-1] == -1的提前返回；用例A = [1, 2, -1]、B = 2→dp[2]被设为 -1，起点算出一条「代价 0」的伪路径[1, 3]，正确答案是空数组。- 错误写法：内层不跳过
dp[j]为无穷的下标；用例A = [1, -1, 2]、B = 1→ 从 0 只能跳到不可达的 1，却把无穷加上A[0]得到一个有限大数，dp[0]被误判为可达，返回一条经过-1位置的非法路径。- 错误写法：用
Integer.MAX_VALUE当哨兵并直接做best + A[i]；用例 任意含不可达位置的输入 → 加法溢出成负数，负数比所有真实代价都小，DP 全表被这个「负无穷」污染。- 错误写法：正序遍历
i从 0 到n-2；用例A = [1, 2, 3]、B = 2→ 计算dp[0]时dp[1]、dp[2]还是初始哨兵，全部被跳过，dp[0]保持无穷，返回空数组。- 错误写法：内层上界写成
i + B不与n-1取小；用例A = [1, 2]、B = 5→ 访问dp[5]直接数组越界。- 错误写法：并列时更新条件写成
dp[j] <= best；用例A = [0, 0, 0, 0]、B = 3→ 所有候选代价相同，bestJ一路被覆盖成最大的下标，返回[1, 4]而不是字典序更小的[1, 2, 3, 4]。- 错误写法：
next初始化为 0 而不是 -1；用例 任意输入 → 路径恢复的while (cur != -1)永远遇不到终止标记，cur在终点又跳回 0，死循环或路径无限增长。- 错误写法：状态定义成「从起点到
i的最小代价」并记录前驱，却忘记最后把路径反转；用例A = [1, 2, 4, -1, 2]、B = 2→ 返回[5, 3, 1]，顺序颠倒判错。- 错误写法：把
dp[i]的含义写成「不含A[i]的后续代价」，转移时却又加上了A[i]；用例A = [1, 1]、B = 1→ 起点或终点的代价被重复计入或整段漏计，总代价与真实路径对不上。- 错误写法：起点是
-1时不做处理，直接从dp[0]恢复路径；用例A = [-1, 2]、B = 1→ 循环里i = 0被continue跳过使dp[0]保持无穷，若忘记检查dp[0]是否为哨兵就会顺着next[0] = -1返回[1]这条非法路径。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 45. 跳跃游戏 II | 中等 | 每步代价恒为 1 且无障碍，可用贪心把 $O(nB)$ 压成 $O(n)$，无需记路径 |
| 55. 跳跃游戏 | 中等 | 只问可达性不问代价，维护一个最远可达边界即可，连 DP 表都不用开 |
| 64. 最小路径和 | 中等 | 转移方向固定为两种且状态是二维网格，同样可加前驱数组来还原具体路径 |