Coin path

Array Dynamic Programming

34.2% acceptance

Mar 31, 2026

260

115

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn cheapest_jump(coins: Vec<i32>, max_jump: i32) -> Vec<i32> {
    let n = coins.len();
    if n == 0 || coins[n - 1] == -1 { return vec![]; }
    let max_jump = max_jump as usize;
    let mut dp = vec![i64::MAX; n];
    let mut next = vec![-1i32; n];
    dp[n - 1] = coins[n - 1] as i64;
    
    for i in (0..n - 1).rev() {
      if coins[i] == -1 { continue; }
      for j in (i + 1)..=((i + max_jump).min(n - 1)) {
        if dp[j] == i64::MAX { continue; }
        let cost = dp[j] + coins[i] as i64;
        if cost < dp[i] {
          dp[i] = cost;
          next[i] = j as i32;
        }
      }
    }
    
    if dp[0] == i64::MAX { return vec![]; }
    let mut result = vec![];
    let mut i = 0i32;
    while i != -1 {
      result.push(i + 1); // 1-indexed
      i = next[i as usize];
    }
    result
  }
}