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


  • 0

    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) {
                res.add(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) {
                    res.add(i+1);
                    tot -= A[i];
                }
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.