Given an arrayA(index starts at1) consisting of N integers: A1, A2, ..., AN and an integerB. The integerBdenotes that from any place (suppose the index isi) in the arrayA, you can jump to any one of the place in the arrayAindexedi+1,i+2, …,i+Bif this place can be jumped to. Also, if you step on the indexi, you have to pay Ai coins. If Ai is -1, it means you can’t jump to the place indexediin the array.

Now, you start from the place indexed1in the arrayA, and your aim is to reach the place indexedNusing 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 indexedNusing 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.

Example 1:

Input:
 [1,2,4,-1,2], 2

Output:
 [1,3,5]

Example 2:

Input:
 [1,2,4,-1,2], 1

Output:
 []

Note:

1. Path Pa1, Pa2, ..., Pan is lexicographically smaller than Pb1, Pb2, ..., Pbm, if and only if at the firstiewhere Pai and Pbi differ, Pai< Pbi; when no such i exists, then n<m.
2. A1>= 0. A2, ..., AN (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].

Discussion

Method:

dp1 calculate min cost, dp2 track jump to.

class Solution {
public:
    vector<int> cheapestJump(vector<int>& A, int B) {
        vector<int> ans;
        if (A.empty() || A.back() == -1) return ans;
        int n = A.size();
        vector<int> dp(n, INT_MAX), pos(n, -1);
        dp[n-1] = A[n-1];
        // working backward
        for (int i = n-2; i >= 0; i--) {
            if (A[i] == -1) continue;
            for (int j = i+1; j <= min(i+B, n-1); j++) {
                if (dp[j] == INT_MAX) continue;
                if (A[i]+dp[j] < dp[i]) {
                    dp[i] = A[i]+dp[j];
                    pos[i] = j;
                }
            }
        }
        // cannot jump to An
        if (dp[0] == INT_MAX) return ans;
        int k = 0;
        while (k != -1) {
            ans.push_back(k+1);
            k = pos[k];
        }
        return ans;
    }
};