Given an array A (index starts at 1) consisting of N integers: A1, A2, ..., AN and an integer B. The integer B denotes that from any place (suppose the index is i) in the array A, you can jump to any one of the place in the array A indexed i+1, i+2, …, i+B if this place can be jumped to. Also, if you step on the index i, you have to pay Ai coins. If Ai is -1, it means you can’t jump to the place indexed i in the array.
Now, you start from the place indexed 1 in the array A, and your aim is to reach the place indexed N using the minimum coins. You need to return the path of indexes (starting from 1 to N) in the array you should take to get to the place indexed N using minimum coins.
If there are multiple paths with the same cost, return the lexicographically smallest such path.
If it's not possible to reach the place indexed N then you need to return an empty array.
Example 1:
Input: [1,2,4,-1,2], 2 Output: [1,3,5]
Example 2:
Input: [1,2,4,-1,2], 1 Output: []
Note:
Path Pa1, Pa2, ..., Pan is lexicographically smaller than Pb1, Pb2, ..., Pbm, if and only if at the first i where Pai and Pbi differ, Pai < Pbi; when no such i exists, then n < m.A1 >= 0. A2, ..., AN (if exist) will in the range of [-1, 100].Length of A is in the range of [1, 1000].B is in the range of [1, 100]. 思路：刚看到题目，第一想到的是Dijkstra算法，之前也遇到一些这种求最短路径并打印路径的问题，‘但是考虑到LC没有出现过Dijkstra算法的题目，转而考虑DP 只求一个值DP就很简单，但是要打印路径，那就在求DP数组的过程中同步更新最优路径（类似于Dijkstra算法），考虑到需要用List记录每次更新都要复制一份，先用String存起来，最后在转成List，用String的一个坏处就是比较路径是要先转换成数组形式 import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { public List<Integer> cheapestJump(int[] A, int B) { List<String> l = new ArrayList<String>(); for(int i=0; i<=A.length; i++) l.add(1+","); int[] dp = new int[A.length]; Arrays.fill(dp, 999999); dp[0] = 0; for(int i=1; i<A.length; i++) { if(A[i] == -1) continue; for(int j=1; j<=B && i-j>=0; j++) { if(dp[i-j]+A[i] < dp[i]) { dp[i] = dp[i-j]+A[i]; l.set(i+1, l.get(i-j+1)+(i+1)+","); } else if(dp[i-j]+A[i] == dp[i] && smaller(l.get(i-j+1)+(i+1)+",", l.get(i+1))) { l.set(i+1, l.get(i-j+1)+(i+1)+","); } } } List<Integer> ret = new ArrayList<Integer>(); if(A[A.length-1] == -1 || dp[dp.length-1] == 999999) return ret; String[] ss = l.get(A.length).split(","); for(String s : ss) ret.add(Integer.valueOf(s)); return ret; } private boolean smaller(String s1, String s2) { String[] ss1 = s1.split(","), ss2 = s2.split(","); for(int i=0; i<ss1.length && i<ss2.length; i++) if(Integer.valueOf(ss1[i]) < Integer.valueOf(ss2[i])) return true; else if(Integer.valueOf(ss1[i]) >Integer.valueOf(ss2[i])) return false; return ss1.length < ss2.length; } }