Problem#
You are given an integer array coins (1-indexed ) of length n and an integer maxJump. You can jump to any index i of the array coins if
coins[i] != -1 and you have to pay coins[i] when you visit index i. In addition to that, if you are currently at index i, you can only jump to any index i + k where i + k <= n and k is a value in the range [1, maxJump].
You are initially positioned at index 1 (coins[1] is not -1). You want to find the path that reaches index n with the minimum cost.
Return an integer array of the indices that you will visit in order so that you can reach index n with the minimum cost. If there are multiple paths with the same cost, return the lexicographically smallest such path. If it is not possible to reach index n, return an empty array.
A path p1 = [Pa1, Pa2, ..., Pax] of length x is lexicographically smaller than p2 = [Pb1, Pb2, ..., Pbx] of length y, if and only if at the first j where Paj and Pbj differ, Paj < Pbj; when no such j
exists, then x < y.
Examples#
Example 1:
1
2
Input: coins = [ 1 , 2 , 4 ,- 1 , 2 ], maxJump = 2
Output: [ 1 , 3 , 5 ]
Example 2:
1
2
Input: coins = [ 1 , 2 , 4 ,- 1 , 2 ], maxJump = 1
Output: []
Constraints:
1 <= coins.length <= 1000-1 <= coins[i] <= 100coins[1] != -11 <= maxJump <= 100
Solution#
Method 1 – Dynamic Programming with Path Reconstruction#
Intuition#
Use DP to find the minimum cost to reach each index. For lexicographically smallest path, always update the path if a new minimum is found or if the path is smaller.
Approach#
Let dp[i] be the minimum cost to reach index i (1-based). Initialize dp[0]=coins[0], others to inf.
For each index i, try all jumps k in [1, maxJump] to i+k if coins[i+k] != -1.
If a new minimum is found for dp[i+k], update dp[i+k] and record the path.
At the end, reconstruct the path from the recorded previous indices.
If dp[n-1] is inf, return empty array.
Complexity#
⏰ Time complexity: O(n * maxJump), because for each of the n positions, we check up to maxJump next positions.
🧺 Space complexity: O(n), as we store DP and previous index arrays of size n.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
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
class Solution {
public :
vector< int > cheapestJump(vector< int >& coins, int maxJump) {
int n = coins.size();
vector< int > dp(n, INT_MAX), prev(n, - 1 );
dp[0 ] = coins[0 ];
for (int i = 0 ; i < n; ++ i) {
if (coins[i] == - 1 || dp[i] == INT_MAX) continue ;
for (int j = i+ 1 ; j <= min(i+ maxJump, n- 1 ); ++ j) {
if (coins[j] == - 1 ) continue ;
int cost = dp[i] + coins[j];
if (cost < dp[j]) {
dp[j] = cost;
prev[j] = i;
} else if (cost == dp[j] && prev[j] > i) {
prev[j] = i;
}
}
}
if (dp[n- 1 ] == INT_MAX) return {};
vector< int > path;
for (int idx = n- 1 ; idx != - 1 ; idx = prev[idx]) path.push_back(idx+ 1 );
reverse(path.begin(), path.end());
return path;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type Solution struct {}
func (Solution ) CheapestJump (coins []int , maxJump int ) []int {
n := len(coins )
dp := make([]int , n )
prev := make([]int , n )
for i := range dp { dp [i ] = 1 << 31 - 1 ; prev [i ] = - 1 }
dp [0 ] = coins [0 ]
for i := 0 ; i < n ; i ++ {
if coins [i ] == - 1 || dp [i ] == 1 << 31 - 1 { continue }
for j := i + 1 ; j <= i + maxJump && j < n ; j ++ {
if coins [j ] == - 1 { continue }
cost := dp [i ] + coins [j ]
if cost < dp [j ] {
dp [j ] = cost ; prev [j ] = i
} else if cost == dp [j ] && prev [j ] > i {
prev [j ] = i
}
}
}
if dp [n - 1 ] == 1 << 31 - 1 { return []int {} }
path := []int {}
for idx := n - 1 ; idx != - 1 ; idx = prev [idx ] { path = append([]int {idx + 1 }, path ... ) }
return path
}
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
class Solution {
public List< Integer> cheapestJump (int [] coins, int maxJump) {
int n = coins.length ;
int [] dp = new int [ n] ;
int [] prev = new int [ n] ;
Arrays.fill (dp, Integer.MAX_VALUE );
Arrays.fill (prev, - 1);
dp[ 0] = coins[ 0] ;
for (int i = 0; i < n; ++ i) {
if (coins[ i] == - 1 || dp[ i] == Integer.MAX_VALUE ) continue ;
for (int j = i+ 1; j <= Math.min (i+ maxJump, n- 1); ++ j) {
if (coins[ j] == - 1) continue ;
int cost = dp[ i] + coins[ j] ;
if (cost < dp[ j] ) {
dp[ j] = cost;
prev[ j] = i;
} else if (cost == dp[ j] && prev[ j] > i) {
prev[ j] = i;
}
}
}
if (dp[ n- 1] == Integer.MAX_VALUE ) return new ArrayList<> ();
LinkedList< Integer> path = new LinkedList<> ();
for (int idx = n- 1; idx != - 1; idx = prev[ idx] ) path.addFirst (idx+ 1);
return path;
}
}
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
class Solution {
fun cheapestJump (coins: IntArray, maxJump: Int): List<Int> {
val n = coins.size
val dp = IntArray(n) { Int .MAX_VALUE }
val prev = IntArray(n) { -1 }
dp[0 ] = coins[0 ]
for (i in 0 until n) {
if (coins[i] == -1 || dp[i] == Int .MAX_VALUE) continue
for (j in i+1. .minOf(i+maxJump, n-1 )) {
if (coins[j] == -1 ) continue
val cost = dp[i] + coins[j]
if (cost < dp[j]) {
dp[j] = cost
prev[j] = i
} else if (cost == dp[j] && prev[j] > i) {
prev[j] = i
}
}
}
if (dp[n-1 ] == Int .MAX_VALUE) return emptyList()
val path = mutableListOf<Int>()
var idx = n-1
while (idx != -1 ) {
path.add(idx+1 )
idx = prev[idx]
}
return path.reversed()
}
}
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
class Solution :
def cheapestJump (self, coins: list[int], maxJump: int) -> list[int]:
n = len(coins)
dp = [float('inf' )] * n
prev = [- 1 ] * n
dp[0 ] = coins[0 ]
for i in range(n):
if coins[i] == - 1 or dp[i] == float('inf' ):
continue
for j in range(i+ 1 , min(i+ maxJump+ 1 , n)):
if coins[j] == - 1 :
continue
cost = dp[i] + coins[j]
if cost < dp[j]:
dp[j] = cost
prev[j] = i
elif cost == dp[j] and prev[j] > i:
prev[j] = i
if dp[- 1 ] == float('inf' ):
return []
path = []
idx = n- 1
while idx != - 1 :
path. append(idx+ 1 )
idx = prev[idx]
return path[::- 1 ]
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
impl Solution {
pub fn cheapest_jump (coins: Vec< i32 > , max_jump: i32 ) -> Vec< i32 > {
let n = coins.len();
let mut dp = vec! [i32 ::MAX ; n];
let mut prev = vec! [- 1 ; n];
dp[0 ] = coins[0 ];
for i in 0 .. n {
if coins[i] == - 1 || dp[i] == i32 ::MAX { continue ; }
for j in i+ 1 ..= std::cmp::min(i+ max_jump as usize , n- 1 ) {
if coins[j] == - 1 { continue ; }
let cost = dp[i] + coins[j];
if cost < dp[j] {
dp[j] = cost;
prev[j] = i as i32 ;
} else if cost == dp[j] && prev[j] > i as i32 {
prev[j] = i as i32 ;
}
}
}
if dp[n- 1 ] == i32 ::MAX { return vec! []; }
let mut path = vec! [];
let mut idx = n as i32 - 1 ;
while idx != - 1 {
path.push(idx+ 1 );
idx = prev[idx as usize ];
}
path.reverse();
path
}
}
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
class Solution {
cheapestJump (coins : number [], maxJump : number ): number [] {
const n = coins .length ;
const dp = Array(n ).fill (Number.POSITIVE_INFINITY );
const prev = Array(n ).fill (- 1 );
dp [0 ] = coins [0 ];
for (let i = 0 ; i < n ; ++ i ) {
if (coins [i ] === - 1 || dp [i ] === Number.POSITIVE_INFINITY ) continue ;
for (let j = i + 1 ; j <= Math.min (i + maxJump , n - 1 ); ++ j ) {
if (coins [j ] === - 1 ) continue ;
const cost = dp [i ] + coins [j ];
if (cost < dp [j ]) {
dp [j ] = cost ;
prev [j ] = i ;
} else if (cost === dp [j ] && prev [j ] > i ) {
prev [j ] = i ;
}
}
}
if (dp [n - 1 ] === Number.POSITIVE_INFINITY ) return [];
const path : number [] = [];
let idx = n - 1 ;
while (idx !== - 1 ) {
path .push (idx + 1 );
idx = prev [idx ];
}
return path .reverse ();