In case we're allowed to change the input array !

class Solution { public: vector<int> cheapestJump(vector<int>& A, int B) { int N = A.size(); if (A[N-1]==-1 || A[0]==-1) return {}; vector<int> next(N, -1); next[N-1] = N; for (int i=N-1;i>=1;i--){ if (A[i-1]==-1) continue; int mini=INT_MAX; for (int j=i+1;j<=min(N, i+B);j++){ if (A[j-1]==-1) continue; if (A[j-1]<mini){ mini = A[j-1]; next[i-1] = j-1; } } if (mini != INT_MAX){ A[i-1] += mini; }else A[i-1] = -1; } vector<int> res; res.push_back(1); int idx = next[0]; while (idx != N){ if (idx==-1) return {}; res.push_back(idx+1); idx = next[idx]; } return res; } };Coin Path