Coin Path

hard dp greedy

Problem

Hop forward up to maxJumps steps. coins[i] = -1 is blocked. Return lexicographically smallest path of indices (1-indexed) from 0 to n−1 with minimum coin sum.

Inputcoins=[1,2,4,-1,2] maxJumps=2

Output[1,3,5]

Path 1→3→5 costs 1+4+2=7.

input

def cheapest_jump(c, k):
    n = len(c)
    if c[-1] == -1: return []
    dp = [10**18] * n; nxt = [-1] * n; dp[-1] = c[-1]
    for i in range(n - 2, -1, -1):
        if c[i] == -1: continue
        for j in range(1, k + 1):
            if i + j < n and dp[i+j] < 10**18 and c[i] + dp[i+j] < dp[i]:
                dp[i] = c[i] + dp[i+j]; nxt[i] = i + j
    if dp[0] == 10**18: return []
    out, i = [], 0
    while i != -1: out.append(i + 1); i = nxt[i]
    return out

function cheapestJump(c, k) {
  const n = c.length; if (c[n - 1] === -1) return [];
  const dp = new Array(n).fill(Infinity); const nxt = new Array(n).fill(-1); dp[n - 1] = c[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    if (c[i] === -1) continue;
    for (let j = 1; j <= k; j++)
      if (i + j < n && dp[i + j] < Infinity && c[i] + dp[i + j] < dp[i]) { dp[i] = c[i] + dp[i + j]; nxt[i] = i + j; }
  }
  if (!isFinite(dp[0])) return [];
  const out = []; let i = 0;
  while (i !== -1) { out.push(i + 1); i = nxt[i]; }
  return out;
}

List cheapestJump(int[] c, int k) {
    int n = c.length; if (c[n - 1] == -1) return new ArrayList<>();
    long[] dp = new long[n]; int[] nxt = new int[n]; Arrays.fill(dp, Long.MAX_VALUE); Arrays.fill(nxt, -1);
    dp[n - 1] = c[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        if (c[i] == -1) continue;
        for (int j = 1; j <= k; j++)
            if (i + j < n && dp[i + j] != Long.MAX_VALUE && c[i] + dp[i + j] < dp[i]) { dp[i] = c[i] + dp[i + j]; nxt[i] = i + j; }
    }
    List out = new ArrayList<>();
    if (dp[0] == Long.MAX_VALUE) return out;
    int i = 0; while (i != -1) { out.add(i + 1); i = nxt[i]; }
    return out;
}

vector cheapestJump(vector& c, int k) {
    int n = c.size(); if (c[n - 1] == -1) return {};
    vector dp(n, LLONG_MAX); vector nxt(n, -1); dp[n - 1] = c[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        if (c[i] == -1) continue;
        for (int j = 1; j <= k; j++)
            if (i + j < n && dp[i + j] != LLONG_MAX && c[i] + dp[i + j] < dp[i]) { dp[i] = c[i] + dp[i + j]; nxt[i] = i + j; }
    }
    if (dp[0] == LLONG_MAX) return {};
    vector out; int i = 0;
    while (i != -1) { out.push_back(i + 1); i = nxt[i]; }
    return out;
}

Explanation

We want the cheapest path from the first index to the last, jumping forward up to maxJumps at a time, and among all cheapest paths we want the lexicographically smallest list of indices. The trick is to work right to left so every jump target is already solved.

dp[i] = the minimum total coins to get from index i to the end. We start with dp[n-1] = c[n-1] (already at the goal) and skip any blocked cell where c[i] == -1.

For each index i, we look at jumps j = 1..k to i + j. We pick the jump that gives the smallest cost c[i] + dp[i+j] and store the chosen landing index in nxt[i]. Because we test j from small to large and only update on a strictly smaller cost, ties keep the earliest (smallest-index) jump, which guarantees the lexicographically smallest path.

Finally we rebuild the route by following nxt from index 0, converting to 1-based indices. If dp[0] is still infinity, no valid path exists and we return an empty list.

Example: coins=[1,2,4,-1,2], maxJumps=2. The cheapest route is 0 → 2 → 4 costing 1+4+2=7, which in 1-based indices is [1, 3, 5].

Time: O(n·k) Space: O(n)