1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| from typing import List
class Solution:
def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:
ans = []
if not coins or coins[-1] == -1:
return ans
n = len(coins)
dp = [float('inf')] * n
pos = [-1] * n
dp[n-1] = coins[n-1]
# working backward
for i in range(n-2, -1, -1):
if coins[i] == -1:
continue
for j in range(i+1, min(i+maxJump, n-1)+1):
if dp[j] == float('inf'):
continue
if coins[i] + dp[j] < dp[i]:
dp[i] = coins[i] + dp[j]
pos[i] = j
# cannot jump to the last coin
if dp[0] == float('inf'):
return ans
k = 0
while k != -1:
ans.append(k + 1)
k = pos[k]
return ans
|