656 Coin Path

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);
    }

656 Coin Path

推荐阅读更多精彩内容