Coin Path

Given an array A (index starts at 1) consisting of N integers: A1, A2, ..., AN and an integer B. The integer B denotes that from any place (suppose the index is i) in the array A, you can jump to any one of the place in the array A indexed i+1, i+2, …, i+B if this place can be jumped to. Also, if you step on the index i, you have to pay Ai coins. If Ai is -1, it means you can’t jump to the place indexed i in the array.

Now, you start from the place indexed 1 in the array A, and your aim is to reach the place indexed N using the minimum coins. You need to return the path of indexes (starting from 1 to N) in the array you should take to get to the place indexed N using minimum coins.

If there are multiple paths with the same cost, return the lexicographically smallest such path.

If it's not possible to reach the place indexed N then you need to return an empty array.

1. Path Pa1, Pa2, ..., Pan is lexicographically smaller than Pb1, Pb2, ..., Pbm, if and only if at the first i where Pai and Pbi differ, Pai < Pbi; when no such i exists, then n < m.

2. A[0] >= 0. A[1], ..., A[N-1] (if exist) will in the range of [-1, 100].

3. Length of A is in the range of [1, 1000].

4. B is in the range of [1, 100].

Example

Example 1:

Input：[1,2,3,4,5]，B=2
Output：[1,3,5]
Explanation：9 is the smallest cost

Example 2:

Input：[1,2,4,-1,2]，B=1
Output：[]
Explanation：There is no path from 1 to n

public class Solution {
    public List<Integer> cheapestJump(int[] A, int B) {
        int[] dp = new int[A.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[A.length - 1] = A[A.length - 1];
        // O(N*B)
        for (int i = A.length - 2; i >= 0; i--) {
            if (A[i] == -1)
                continue;
            for (int j = i + 1; j < A.length && j <= i + B; j++) {
                if (A[j] != -1 && dp[j] != Integer.MAX_VALUE && dp[j] + A[i] < dp[i])
                    dp[i] = dp[j] + A[i];
            }
        }
        List<Integer> ans = new ArrayList<>();
        if (dp[0] == Integer.MAX_VALUE)
            return ans;
        // Backtracking for path (index path)
        int i = 0;
        ans.add(0 + 1);
        while (i != A.length - 1) {
            int required = dp[i] - A[i];
            int nextIndex = -1;
            for (int j = i + 1; j <= i + B && j < A.length; j++) {
                if (dp[j] == required) {
                    nextIndex = j;
                    break;
                }
            }
            i = nextIndex;
            ans.add(i + 1);
        }
        return ans;
    }
}