Leetcode Problem 656. Coin Path

656. Coin Path

Leetcode Solutions

Initialize dp and next arrays of size n with dp[n-1] = coins[n-1] and next[n-1] = -1.
Loop over the array from the second last index down to the first index.
For each index i, initialize min_cost to infinity and min_index to -1.
Loop from i+1 to i+maxJump (inclusive) and within the bounds of the array.
For each possible jump j, if coins[j] is not -1 and dp[j] + coins[i] is less than min_cost, update min_cost and min_index.
Set dp[i] to min_cost and next[i] to min_index.
After filling dp and next, initialize the result list res with the first index 1.
Loop from the first index using next to construct the path and add each index to res.
If at any point next[i] is -1, return an empty list as it's not possible to reach the end.
Return the res list.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen