https://leetcode.com/problems/coin-path/description/
首先这道题看上去可以用Dijkstra做。 最小路径嘛，又带了权重，那Dijstra最合适，不过他要求的是path不是 path的长度，所以还得记一个从哪里来的。我最初是思路是从前往后找，然后找完之后从尾向前重建路径。 但是我写完之后发现解决不了lexicographical order的问题。有一个test case“ [0,0,0,0,0,0]， 3 ” 解决不了。 果断看答案，发现是用dp而且是从后向前倒推再从前向后重建路径，跟我的作法正好反过来。
这一点比较坑（如何解决lexicographical order），我第二遍做时还是花了不少时间。
下面解释一下我看来的答案。
1。 最外层的顺序从最后一个点开始倒推。每个点的DP状态记录这个点到终点的最少花费。如果从这个点到不了终点，就是-1；
2。对于每个点求他dp值的时候又是从左向右推。这样可以保证lexicographical order。如果后面出现的值和当前一样，那还是留之前的，因为之前的lexicographical order比较小。
这两个trick都是平淡无奇但结合在一起就能完美解决这道题。
后来发现这个挺绕的思路可以直接从recursion + mem推导出来。
如果从recursion的思路就比较直接了。 所以一定要一题会多解，这样这条路遇到问题我们可以从袖子里掏出另外一个trick来。
用Dijkstra方法就不是很方便做。当然我在leetcode论坛上也看到有人用Dijkstra做，不过那个代码实在是太难看了。
下面是DP代码，新手可以略过直接看recursion的。
public List<Integer> cheapestJump(int[] A, int B) {
int N = A.length; //省得老写A.length好麻烦
List<Integer> ans = new LinkedList<>();
int[] dp = new int[N];
//dp state: the min cost from the end;
Arrays.fill(dp, -1);
dp[N - 1] = A[N - 1]; // 初始化
Map<Integer, Integer> leftRightMap = new HashMap<>();
// 这个map从左边的点指向他右边的点，
//由于这里是倒着找的， parentChild有点confusing，
//所以用leftRight而不是parentChild,
for (int i = N - 2; i >= 0; i--){ //从右向左
if (A[i] == -1) continue;
for (int b = 1; b <= B && b + i < N; b++) { //从左向右
if (A[b + i] == -1 ||dp[i + b] == -1) continue;
if (dp[i] == -1 || dp[b + i] + A[i] < dp[i]) {
dp[i] = dp[b + i] + A[i];
// 现在记一下从i点去哪个点总cost小，
leftRightMap.put(i, i + b);
}
}
}
if (dp[0] == -1) return ans;
Integer cur = 0;
while (cur != null) {
ans.add(cur + 1);
cur = leftRightMap.get(cur);
}
return ans;
用Recursion + memorization的办法解相比就直观多了。
我建议如果面试中如果被问到这道题，先propose recursion + Memorization吧, 这样保证lexicographical order没有问题。下面是代码， 没有DP好看，但好懂呀
public List<Integer> cheapestJump(int[] A, int B) {
List<Integer> ans = new LinkedList<>();
int N = A.length;
if (A[N - 1] == -1) return ans;
Map<Integer, Integer> leftRightMap = new HashMap<>();
Map<Integer, Integer> costMap = new HashMap<>();
if (cheapestJump(A, B, 0, leftRightMap, costMap, N) == -1) {
return ans;
}
// reconstruct Map;
Integer cur = 0;
while (cur != null) {
ans.add(cur + 1); //indexed from 1
cur = leftRightMap.get(cur);
}
return ans;
}
private int cheapestJump(int[] A, int B, int index,
Map<Integer, Integer> leftRightMap,
Map<Integer, Integer> costMap, int N) {
if (index >= N ) return -1;
if (costMap.containsKey(index)) return costMap.get(index);
if (index == N - 1 && A[index] != -1) {
costMap.put(index, A[index]);
return costMap.get(index);
}
if (A[index] == -1) {
costMap.put(index, -1);
return costMap.get(index);
}
int localMin = -1, right = -1;
for (int step = 1; step <= B; step++) {
int cost = cheapestJump(A, B, step + index, leftRightMap, costMap, N);
if (cost != -1) {
if (localMin == -1 || cost < localMin){
localMin = cost;
right = step + index;
}
}
}
costMap.put(index, localMin != -1 ? localMin + A[index] : -1);
leftRightMap.put(index, right);
return costMap.get(index);
}
