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

• 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;
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){
cur=trace[cur];
}
return res;
}
}
``````

• 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.

• This post is deleted!

• 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

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