Leetcode 656. Coin Path
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
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.