Java O(nB) time, O(n) space DP


  • 0
    S

    May not be the optimal one, but really easy to be understood. Willing to know any better solution.

    public class Solution {
        public List<Integer> cheapestJump(int[] A, int B) {
            List<Integer> res=new ArrayList<>();
            if (A.length==0 || A[A.length-1]==-1 || A[0]==-1) return res;
            if (A.length==1) {res.add(1); return res;}
            int[] steps=new int[A.length];  //keep track of cost
            int[] trace=new int[A.length];  //keep track of prev element
            int[] len=new int[A.length];  //keep track of sequence length to reach an element
            Arrays.fill(steps, Integer.MAX_VALUE);
            Arrays.fill(trace, -1);
            steps[0]=0;
            len[0]=1;
            for (int i=1; i<A.length; i++){
                if (A[i]==-1) continue;
                /*
                We trace from i-B to i-1 to get the min lexi result 
                for example, in [1,3,2,4], 2, [1,2,4] is smaller than [1,3,4]
                */
                for (int j=Math.max(i-B, 0); j<i; j++){
                    //we want the min cost
                    if (steps[j]!=Integer.MAX_VALUE && steps[j]+A[j]<steps[i]){
                        steps[i]=steps[j]+A[j];
                        trace[i]=j;
                        len[i]=len[j]+1;
                    }
                    //if the cost is same but our new sequence is longer than our prev one, note j<i, so add j before i in the sequence will definitely get a lexi smaller result
                    else if (steps[j]!=Integer.MAX_VALUE && steps[j]+A[j]==steps[i]){
                        if (len[j]+1>len[i]){
                            trace[i]=j;
                            len[i]=len[j]+1;
                        }
                    }
                }
            }
            int cur=A.length-1;
            if (trace[cur]==-1) return res;
            while (cur!=0){
                res.add(0, cur+1);
                cur=trace[cur];
            }
            res.add(0, 1);
            return res;
        }
    }
    

  • 0
    Z

    May I ask why is that "if the cost is same but our new sequence is longer than our prev one, note j<i, so add j before i in the sequence will definitely get a lexi smaller result"?
    I admit at the position of i here, those j which j <i may be smaller than i. But previous to this position, how can we know their lexicographically large. I think it's unknown. Maybe I just haven't understood the relationship between length and lexicographically large. And hope for your explanation.
    Thank you.


  • 0
    S
    This post is deleted!

  • 0
    Z

    @zengc said in Java O(nB) time, O(n) space DP:

    May I ask why is that "if the cost is same but our new sequence is longer than our prev one, note j<i, so add j before i in the sequence will definitely get a lexi smaller result"?
    I admit at the position of i here, those j which j <i may be smaller than i. But previous to this position, how can we know their lexicographically large. I think it's unknown. Maybe I just haven't understood the relationship between length and lexicographically large. And hope for your explanation.
    Thank you.

    Here is the explanation: https://discuss.leetcode.com/topic/98491/java-22-lines-solution-with-proof


Log in to reply
 

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