Problem Explanation

In the given problem, we have an array A with N integers (A1, A2, ..., AN) and an integer B. The number B represents that from any position (i) in the array A, we can make a jump to the place A[i+1], i+2, ..., i+B, if it's possible. When we step on the position i, we have to spend Ai coins. If Ai is -1, it means that we are unable to jump towards index i position. We are required to find the minimum cost path from index 1 to N and return this path. In case multiple paths have the same cost, we should return the lexicographically smallest path. If we cannot reach the place indexed N, we return an empty array.

Solution Approach

The solution uses a Dynamic Programming approach where we use 2 arrays, "dp" which will store the minimum cost to reach the end from each index, and "next" which will store the next index chosen to be part of the minimum cost path.

We start from the end of the coins array and go back while updating the "dp" array. For every index 'i', we consider all the indices from i+1 to i+B, calculate the total cost from 'i' to the end through each of them and update the dp[i] with the minimum of these costs. We also update 'next[i]' to be the index which gave us the minimum cost.

Once dp[0] is calculated that is the minimum cost from the first index, if its value is INT_MAX, we return an empty list as we cannot reach the end.

If dp[0] is not INT_MAX, we construct the path using the "next" array starting from index 0 until we reach the end.

Python Solution

1
2python
3import sys
4
5class Solution:
6    def cheapestJump(self, coins, B):
7        N = len(coins)
8        if coins[-1] == -1:
9            return []
10
11        # Initializing arrays
12        dp = [float('inf')] * N
13        dp[N - 1] = coins[N - 1]
14        
15        Next = [-1] * N
16        path = []
17        DP = [0] * N
18        DP[N-1] = coins[N-1]
19
20        # Dynamic Programming
21        for i in range(N - 2, -1, -1):
22            if coins[i] == -1:
23                continue
24            for b in range(1, min(B, N - 1 - i) + 1):
25                if dp[i + b] + coins[i] < dp[i]:
26                    dp[i] = dp[i + b] + coins[i]
27                    Next[i] = i + b
28
29        # Constructing the path
30        i = 0
31        while i < N:
32            path.append(i + 1)
33            i = Next[i]
34
35        if path[-1] != N:
36            return []
37
38        return path

Java Solution

1
2java
3class Solution {
4    public int[] cheapestJump(int[] coins, int B) {
5        int N = coins.length;
6        int[] res = new int[N], pos = {-1, -1, 0}, dp = new int[N], next = new int[N];
7        Arrays.fill(dp, -1);
8        if (coins[N - 1] == -1) {
9            return new int[0];
10        }
11        dp[N - 1] = coins[N - 1];
12        dp[N] = next[N] = 0;
13
14        // Dynamic Programming
15        for (int i = N - 2; i >= 0; i--) {
16            if (coins[i] == -1) {
17                continue;
18            }
19            
20            for (int b = 1; b <= Math.min(B, N - 1 - i); b++) {
21                if (dp[i + b] == -1) {
22                    continue;
23                }
24
25                if (dp[i] == -1 || dp[i + b] + coins[i] < dp[i] || dp[i + b] + coins[i] == dp[i] && i + b < next[i]) {
26                    dp[i] = dp[i + b] + coins[i];
27                    next[i] = i + b;
28                } 
29            }
30        }
31
32        // Constructing the path
33        for (int i = 0; i != -1 && i < N; i = next[i]) {
34            res[pos[0]++] = i + 1;
35        }
36
37        if (pos[0] == -1 || res[pos[0] - 1] != N) {
38            return new int[0];
39        }
40
41        return Arrays.copyOf(res, pos[0]);
42    }
43}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<int> cheapestJump(vector<int>& coins, int B) {
6        int N = coins.size();
7        vector<int> dp(N, INT_MAX), next(N, -1), path;
8        
9        dp[N - 1] = coins[N - 1];
10
11        // Dynamic Programming
12        for (int i = N - 2; i >= 0; i--) {
13            if (coins[i] == -1) {
14                continue;
15            }
16            for (int b = 1; b <= min(B, N - 1 - i); b++) {
17                if (dp[i + b] + coins[i] < dp[i]) {
18                    dp[i] = dp[i + b] + coins[i];
19                    next[i] = i + b;
20                }
21            }
22        }
23        
24        // Constructing the path
25        for (int i = 0; i < N; i = next[i]) {
26            path.push_back(i + 1);
27            if (next[i] == -1 && i != N - 1) {
28                return {};
29            }
30        }
31
32        return path;
33    }
34};

JavaScript Solution

1
2javascript
3class Solution {
4    cheapestJump(coins, B) {
5        let N = coins.length;
6        let dp = Array(N).fill(Number.MAX_SAFE_INTEGER);
7        let next = Array(N).fill(-1);
8        let path = [];
9        
10        dp[N - 1] = coins[N - 1];
11
12        // Dynamic Programming
13        for (let i = N - 2; i >= 0; i--) {
14            if (coins[i] == -1) continue;
15
16            for (let b = 1; b <= Math.min(B, N - 1 - i); b++) {
17                if (dp[i + b] + coins[i] < dp[i]) {
18                    dp[i] = dp[i + b] + coins[i];
19                    next[i] = i + b;
20                } 
21            }
22        }
23        
24        // Constructing the path
25        for (let i = 0; i < N; i = next[i]) {
26            path.push(i + 1);
27            if (next[i] == -1 && i != N - 1) {
28                return [];
29            }
30        }
31
32        return path;
33    }
34}
35´´´
36
37# C# Solution

csharp public class Solution { public int[] CheapestJump(int[] coins, int B) { int N = coins.Length; int[] dp = new int[N]; int[] next = new int[N]; List path = new List();

1    dp[N - 1] = coins[N - 1];
2
3    // Dynamic Programming
4    for (int i = N - 2; i >= 0; i--) {
5        if (coins[i] == -1) {
6            continue;
7        }
8        for (int b = 1; b <= Math.Min(B, N - 1 - i); b++) {
9            if (dp[i + b] + coins[i] < dp[i]) {
10                dp[i] = dp[i + b] + coins[i];
11                next[i] = i + b;
12            } 
13        }
14    }
15    
16    // Constructing the path
17    for (int i = 0; i < N; i = next[i]) {
18        path.Add(i + 1);
19        if (next[i] == -1 && i != N - 1) {
20            return new int[0];
21        }
22    }
23
24    return path.ToArray();
25}

}

1
2# C Solution
3

C #include <stdlib.h> #include <limits.h>

// Solution

int* cheapestJump(int* coins, int coinsSize, int B, int* returnSize){ int i, b, n = coinsSize, *next = malloc(sizeof(int) * (n + 1)), *dp = malloc(sizeof(int) * (n + 1)), *res;

1dp[n] = next[n] = 0;
2for(i = 0; i < n; ++i){
3    dp[i] = coins[i] == -1 ? -1 : INT_MAX;
4    next[i] = -1;
5}
6if(coins[n - 1] != -1){
7    dp[n - 1] = coins[n - 1];
8}
9
10// Dynamic Programming
11for(i = n - 2; i >= 0; --i){
12    if(coins[i] == -1){
13        continue;
14    }
15    for(b = 1; b <= B && i + b < n; ++b){
16        if(dp[i + b] == -1) {
17            continue;
18        }
19        if(dp[i + b] + coins[i] < dp[i] || dp[i + b] + coins[i] == dp[i] && next[i] > i + b){
20            dp[i] = dp[i + b] + coins[i];
21            next[i] = i + b;
22        }
23    }
24}
25
26// Constructing the path
27for(i = 0, *returnSize = 0; dp[i] != -1 && i < n; i = next[i]){
28    ++*returnSize;
29}
30res = *returnSize > 0 ? malloc(sizeof(int) * *returnSize) : NULL;
31for(i = 0, *returnSize = 0; dp[i] != -1 && i < n; i = next[i]){
32    res[(*returnSize)++] = i + 1;
33}
34
35// Free temporary arrays
36free(next);
37free(dp);
38
39return dp[0] == -1 ? NULL : res;

}

1
2 C
3
4Above solution first checks if the start and end points are valid (i.e., not equal to -1). If they are valid, it initializes the dp and next arrays with appropriate values. Then it implements the dynamic programming solution to update the dp and next arrays. Finally, it constructs and returns the path if it's possible to reach from the first index to the last index following the conditions. Otherwise, it returns NULL.