The Coin Path problem asks you to find the cheapest path from the start to the end of an array of coins, where each coin has a cost. You are given:
A of length n, where A[i] is the cost to step on the i-th position. If A[i] == -1, that position is blocked and cannot be stepped on.B (1 ≤ B ≤ n), representing the maximum number of steps you can jump forward from your current position.
Starting at index 0, your goal is to reach index n-1 (the end) with the minimum total cost. At each step, you can jump forward at most B positions, but only onto unblocked positions (A[j] != -1). You must return the path as a list of 1-based indices. If there are multiple paths with the same minimum cost, return the lexicographically smallest one. If it's impossible to reach the end, return an empty list.
Constraints:
This problem looks a bit like a mix of the minimum path sum and jump game problems. The most basic approach would be to try all possible paths from the start, keeping track of their costs, and picking the cheapest one. However, this brute-force way would be extremely slow for large arrays because the number of possible paths grows exponentially.
We need to optimize. Since each jump is limited to B steps and some positions are blocked, we can use dynamic programming to store the minimum cost to reach each position. By working backwards (from the end to the start), or forwards (from the start to the end), we can efficiently compute the minimum cost to reach the end from each position. Additionally, to reconstruct the path, we keep track of where each minimum cost comes from.
The lexicographical order requirement means that when two paths have the same cost, we should prefer the one that steps to the smallest index next. This can be handled by always updating the path if a cheaper or equally cheap path is found via a smaller index.
We solve this problem using dynamic programming with path reconstruction. Here's a step-by-step breakdown:
dp of size n where dp[i] represents the minimum cost to reach the end from position i.dp[n-1] to A[n-1] (the cost of the last position), unless it's blocked (-1), in which case it's unreachable.next_index array to help reconstruct the path. next_index[i] stores the next position to jump to from i in the optimal path.dp from end to start:
i from n-2 down to 0:A[i] == -1, skip (blocked).j from i+1 to min(i+B, n-1):dp[j] is not inf and A[j] != -1, consider dp[j] + A[i] as a candidate cost.j as the next step if it's cheaper or lexicographically smaller.dp[0] is inf, return an empty list (no path).0 and use next_index to follow the path to the end, collecting 1-based indices.This approach ensures we always pick the cheapest path, and in case of ties, the lexicographically smallest path.
Example:
Input: A = [1,2,4,-1,2], B = 2
Output: [1,3,5]
n = 5dp = [inf, inf, inf, inf, 2] (since A[4]=2 is the last position)next_index = [-1, -1, -1, -1, -1]dp:
A[3] = -1 → blocked, skip.dp[4]=2), so dp[2]=4+2=6, next_index[2]=4.dp[2]=6, so dp[1]=2+6=8, next_index[1]=2.dp[1]=8, 2 has dp[2]=6. 2 is better: dp[0]=1+6=7, next_index[0]=2.[1,3,5].
Brute-force approach:
For each position, try all possible paths recursively. The number of paths can be exponential in n, so the time complexity is O(B^n), which is not feasible for large n.
Dynamic programming approach:
For each position i, we look at at most B next positions. So, total work is O(nB).
Space complexity is O(n) for the dp and next_index arrays.
The Coin Path problem is a classic example of using dynamic programming to efficiently find a minimum-cost path with constraints. By breaking the problem into subproblems (minimum cost to reach the end from each position), and carefully reconstructing the path, we can solve it in O(nB) time. The lexicographical constraint is handled by always preferring smaller next indices in case of ties. This approach is both efficient and elegant, and illustrates the power of dynamic programming for path-finding problems.
class Solution:
def cheapestJump(self, A, B):
n = len(A)
INF = float('inf')
dp = [INF] * n
nxt = [-1] * n
if A[-1] != -1:
dp[-1] = A[-1]
# Fill dp from end to start
for i in range(n - 2, -1, -1):
if A[i] == -1:
continue
for j in range(i + 1, min(i + B + 1, n)):
if dp[j] != INF:
if dp[j] + A[i] < dp[i]:
dp[i] = dp[j] + A[i]
nxt[i] = j
# If unreachable
if dp[0] == INF:
return []
# Reconstruct path
path = []
idx = 0
while idx != -1:
path.append(idx + 1)
idx = nxt[idx]
return path
class Solution {
public:
vector<int> cheapestJump(vector<int>& A, int B) {
int n = A.size();
const int INF = 1e9 + 7;
vector<int> dp(n, INF), next(n, -1);
if (A[n-1] != -1) dp[n-1] = A[n-1];
for (int i = n-2; i >= 0; --i) {
if (A[i] == -1) continue;
for (int j = i+1; j <= min(n-1, i+B); ++j) {
if (dp[j] != INF) {
if (dp[j] + A[i] < dp[i]) {
dp[i] = dp[j] + A[i];
next[i] = j;
}
}
}
}
if (dp[0] == INF) return {};
vector<int> path;
int idx = 0;
while (idx != -1) {
path.push_back(idx + 1);
idx = next[idx];
}
return path;
}
};
class Solution {
public List<Integer> cheapestJump(int[] A, int B) {
int n = A.length;
int INF = Integer.MAX_VALUE / 2;
int[] dp = new int[n];
int[] next = new int[n];
Arrays.fill(dp, INF);
Arrays.fill(next, -1);
if (A[n-1] != -1) dp[n-1] = A[n-1];
for (int i = n-2; i >= 0; --i) {
if (A[i] == -1) continue;
for (int j = i+1; j <= Math.min(i+B, n-1); ++j) {
if (dp[j] != INF) {
if (dp[j] + A[i] < dp[i]) {
dp[i] = dp[j] + A[i];
next[i] = j;
}
}
}
}
List<Integer> res = new ArrayList<>();
if (dp[0] == INF) return res;
int idx = 0;
while (idx != -1) {
res.add(idx + 1);
idx = next[idx];
}
return res;
}
}
var cheapestJump = function(A, B) {
const n = A.length;
const INF = Number.MAX_SAFE_INTEGER;
let dp = new Array(n).fill(INF);
let next = new Array(n).fill(-1);
if (A[n-1] !== -1) dp[n-1] = A[n-1];
for (let i = n-2; i >= 0; --i) {
if (A[i] === -1) continue;
for (let j = i+1; j <= Math.min(i+B, n-1); ++j) {
if (dp[j] !== INF) {
if (dp[j] + A[i] < dp[i]) {
dp[i] = dp[j] + A[i];
next[i] = j;
}
}
}
}
if (dp[0] === INF) return [];
let path = [];
let idx = 0;
while (idx !== -1) {
path.push(idx + 1);
idx = next[idx];
}
return path;
};