# My Java O(nB) time, O(n) space DP solution, with greedy/backtrack to recover the path

• Please check the inline comments. This is a combination of the jump problem and hero with 1 point of health, but instead of greedy searching from the beginning, we should start from the end of the array.

``````class Solution {
public List<Integer> cheapestJump(int[] A, int B) {
List<Integer> res = new ArrayList<>();
if (A == null || A.length == 0 || B <= 0) return res;
int n = A.length;
if (A[0] == -1 || A[n - 1] == -1) return res;
if (A.length == 1) {
return res;
}

int[] dp = new int[n];
// Initial Condition
if (A[n - 1] == -1) return res;
dp[n - 1] = A[n - 1];

for (int i = n - 2; i >= 0; i--) {
int cost = Integer.MAX_VALUE;
int node = -1;
for (int j = Math.min(n - 1, i + B); j > i; j--) {
if (A[j] == -1) continue;
if (cost >= dp[j]) {
cost = dp[j];
node = j;
}
}
if (node == -1) return res;
dp[i] = cost + A[i];
}
int tot = dp[0];
// Use Greedy Strategy to catch the lexicographically smallest list
// tot is the minimum cost, if any subsequent dp (cost) is smaller than it
// means we can take that root to the end
for (int i = 0; i < n; i++) {
if (dp[i] == tot) {