656 Coin Path

656. Coin Path

1. Question

Given an arrayA(index starts at1) consisting of N integers: A1, A2, ..., AN and an integerB. The integerBdenotes that from any place (suppose the index isi) in the arrayA, you can jump to any one of the place in the arrayAindexedi+1,i+2, …,i+Bif this place can be jumped to. Also, if you step on the indexi, you have to pay Ai coins. If Ai is -1, it means you can’t jump to the place indexediin the array.

Now, you start from the place indexed1in the arrayA, and your aim is to reach the place indexedNusing 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 indexedNusing 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:

1. Path Pa1, Pa2, ..., Pan is lexicographically smaller than Pb1, Pb2, ..., Pbm, if and only if at the firsti

   where Pai and Pbi differ, Pai < Pbi; when no such iexists, then n<m.

2. A1 >= 0. A2, ..., AN (if exist) will in the range of [-1, 100].

3. Length of A is in the range of [1, 1000].

4. B is in the range of [1, 100].

2. Implementation

(1) DP

思路: 从后往前扫一遍数组，用两个数组dp和preIndex分别记录以下信息，dp[i]表示从开头到位置i的min cost, preIndex记录在min cost path中位置i前的一个位置

class Solution {
    public List<Integer> cheapestJump(int[] A, int B) {
        List<Integer> res = new ArrayList<>();

        if (A == null || A.length == 0 || A[A.length - 1] == -1) {
            return res;
        }

        int n = A.length;
        // dp[i] is the min cost to reach position i from the start
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n - 1] = A[n - 1];

        // preIndex[i] store the previous index of i in the min cost path
        int[] preIndex = new int[n];
        Arrays.fill(preIndex, -1);

        for (int i = n - 2; i >= 0; i--) {
            // Ignore position we cannot reach
            if (A[i] == -1) continue;
            for (int j = i + 1; j <= Math.min(i + B, n - 1); j++) {
                if (dp[j] == Integer.MAX_VALUE) continue;

                if (A[i] + dp[j] < dp[i]) {
                    dp[i] = A[i] + dp[j];
                    preIndex[i] = j;
                }
            }
        }

        // Cannot reach A[n - 1] from A[0]
        if (dp[0] == Integer.MAX_VALUE) {
            return res;
        }

        for (int index = 0; index != -1; index = preIndex[index]) {
            res.add(index + 1);
        }
        return res;
    }
}

3. Time & Space Complexity

时间复杂度O(n^2), 空间复杂度O(n)