# 656     Coin Path

## 656. [Coin Path](https://leetcode.com/problems/coin-path/description/)

## 1. Question

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:**

1. 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`.
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前的一个位置

```java
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)