LeetCode 656. 成本最小路径
题目描述
题意分析
从数组第一个位置出发，每次向右前进
1..B个位置，不能落到值为-1的位置，跳跃时可以跨过这些位置。每个落脚位置都要支付对应费用，目标是到达最后一个位置的最小费用路径；费用相同则选择下标序列中字典序最小的一条。跳跃方向只能向右，不会形成环。可以从终点向前计算每个位置的最优后缀，再记录下一步来恢复路径，最终输出从
1开始的位置编号。
解法：从后往前 DP + next 恢复路径
核心思路
[!blue]
定义
dp[i]为从位置i到终点的最小费用，包含A[i]本身；无法到达终点时记为INF。终点合法时，dp[n-1] = A[n-1]，因为已经不需要继续跳跃。若终点禁止落脚，整题直接无解。从右往左处理位置
i，它的下一步只能是i+1..min(i+B,n-1)中的某个j，而这些dp[j]都已经计算完成。跳过dp[j] == INF的后继，在可达后继中寻找最小dp[j]，再加上固定的A[i]。若没有可达后继，或者当前位置本身禁止落脚，就保持不可达。用
next[i]记录所选后继。费用相同时应选择下标最小的j：所有候选路径都以i开头，下一步不同就是它们第一个不同的位置，较小的j一定带来较小字典序。若下一步相同，则比较的是该后继的路径，而它已在更早的反向计算中保留了最小费用、最小字典序的后缀。因此局部的平局选择能递推成完整路径的字典序最优。计算完成后，
dp[0] == INF就返回空结果；否则从0不断沿next前进。每次下标严格增大，合法的非终点状态又一定记录了后继，所以最终会到达终点，并由终点的next = -1结束。
解题步骤
- 若终点禁止落脚，返回空结果；否则将所有费用初始化为
INF、所有后继初始化为-1，再设置终点费用。- 从
n-2向0枚举位置，跳过禁止落脚的位置。- 枚举最多
B步内的可达后继，优先最小费用，同费用选择更小后继下标。- 有合法后继时更新
dp[i]和next[i]，没有则保持不可达。- 起点可达时沿
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;
}
}
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)$。每个位置最多检查
B个后继，路径恢复最多再经过n个位置。- 空间复杂度：$O(n)$。保存最小费用和下一步位置，输出路径也不超过
n个位置。
关键点总结
[!green]
- 状态费用包含当前位置，终点也要计费，转移时只加一次
A[i]。- 只向右跳跃使状态图无环，从右向左处理即可先得到全部后继状态。
- 先比较费用，同费用再比较下一步下标；后继已经保留最优后缀，无需复制整条路径。
- 保存后继即可恢复答案，禁止位置和无法到达终点的位置都保持不可达。
易错点总结
[!yellow]
- 把
-1当作负费用参与求最小值，会选中禁止落脚的位置。- 初始化终点费用为零，会漏掉路径中最后一个位置的费用。
- 字典序最小不等于跳跃次数最少；零费用位置可能让更长路径的字典序更小。
- 费用更大时仍优先选较小下标，颠倒了费用与字典序的优先级。
- 起点不可达时仍沿
next输出，会把不完整路径当作答案；有效路径也要记得将下标加一。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 45. 跳跃游戏 II | 中等 | 同样在数组中向前跳有限距离，原题最小化跳数，本题有位置费用、障碍和字典序并列规则。 |
| 64. 最小路径和 | 中等 | 同样在无环状态图上求最小路径和，本题转移来自后续一段下标而非两个网格邻居。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！