难度: Hard
Submission
运行时间: 66 ms
内存: 16.2 MB
class Solution:
def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:
n = len(coins)
if coins[0] == - 1 or coins[-1] == - 1:
return []
nxt = [-1] * n
dp = [float('inf')] * n
dp[-1] = coins[-1]
for i in range(n - 2, - 1, - 1):
if coins[i] == - 1:
continue
for j in range(i + 1, min(n, i + maxJump + 1)):
if dp[i] > dp[j] + coins[i]:
dp[i] = dp[j] + coins[i]
nxt[i] = j
if dp[0] == float('inf'):
return []
res = []
start = 0
while nxt[start] != - 1:
res.append(start + 1)
start = nxt[start]
return res + [n]
Explain
这个题解使用了动态规划的思路。从终点开始倒序遍历数组，对于每个位置，计算从该位置跳到终点的最小花费。状态转移方程为：dp[i] = min(dp[j] + coins[i])，其中 i + 1 <= j <= min(n, i + maxJump + 1)。同时使用 nxt 数组记录每个位置的最优下一跳位置，用于最后重构最小花费路径。
时间复杂度: O(n * maxJump)，最坏情况下为 O(n^2)
空间复杂度: O(n)
class Solution:
def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:
n = len(coins)
if coins[0] == - 1 or coins[-1] == - 1:
return []
# nxt[i] 记录从位置 i 跳到终点的最优下一跳位置
nxt = [-1] * n
# dp[i] 记录从位置 i 跳到终点的最小总花费
dp = [float('inf')] * n
dp[-1] = coins[-1]
# 从后往前遍历数组
for i in range(n - 2, - 1, - 1):
if coins[i] == - 1:
continue
# 遍历从位置 i 起跳，跳 1 ~ maxJump 步到达的下一个位置 j
for j in range(i + 1, min(n, i + maxJump + 1)):
if dp[i] > dp[j] + coins[i]:
dp[i] = dp[j] + coins[i]
nxt[i] = j
# 无法到达终点
if dp[0] == float('inf'):
return []
# 重构最小花费的路径
res = []
start = 0
while nxt[start] != - 1:
res.append(start + 1)
start = nxt[start]
return res + [n]
Explore
倒序遍历数组从终点开始，这样可以确保在计算某个位置 i 的最小花费时，所有可能跳跃到的后续位置 j 的最小花费已经被计算过了。这种方式符合动态规划中的‘无后效性’，即后续的状态不会影响先前的状态。如果从起点开始，我们需要在每次计算时预先知道未来的状态，这在动态规划中通常是不可行的。
直接跳过`coins[i] == -1`的位置是必要的，因为这表示从该位置无法进行任何有效跳跃（视为无法通行的阻碍）。在路径重构时，跳过这些位置不会影响路径的正确性，因为这些位置本身就不应该出现在任何最小花费路径上。
在状态转移方程中，`dp[i]`表示从位置i跳到终点的最小总花费。当考虑从位置i跳到位置j的花费时，我们必须支付从i位置开始的代价`coins[i]`，而`dp[j]`已经包含了从j到终点的最小花费。因此，适合的转移方程是将当前位置的花费与目标位置的已知最小花费相加。
当`maxJump`非常大时，内层循环可能会变得效率低下。一种可能的优化方法是使用数据结构，如线段树或最小堆，这些能够快速检索和更新区间最小值。例如，使用线段树可以在对数时间内进行查询和更新操作，从而减少每次更新`dp[i]`时的时间复杂度。