> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/coin-path.md).

# Coin Path

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.

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. A\[0] >= 0. A\[1], ..., A\[N-1] (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]`.

#### Example

**Example 1:**

```
Input：[1,2,3,4,5]，B=2
Output：[1,3,5]
Explanation：9 is the smallest cost
```

**Example 2:**

```
Input：[1,2,4,-1,2]，B=1
Output：[]
Explanation：There is no path from 1 to n
```

```java
public class Solution {
    public List<Integer> cheapestJump(int[] A, int B) {
        int[] dp = new int[A.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[A.length - 1] = A[A.length - 1];
        // O(N*B)
        for (int i = A.length - 2; i >= 0; i--) {
            if (A[i] == -1)
                continue;
            for (int j = i + 1; j < A.length && j <= i + B; j++) {
                if (A[j] != -1 && dp[j] != Integer.MAX_VALUE && dp[j] + A[i] < dp[i])
                    dp[i] = dp[j] + A[i];
            }
        }
        List<Integer> ans = new ArrayList<>();
        if (dp[0] == Integer.MAX_VALUE)
            return ans;
        // Backtracking for path (index path)
        int i = 0;
        ans.add(0 + 1);
        while (i != A.length - 1) {
            int required = dp[i] - A[i];
            int nextIndex = -1;
            for (int j = i + 1; j <= i + B && j < A.length; j++) {
                if (dp[j] == required) {
                    nextIndex = j;
                    break;
                }
            }
            i = nextIndex;
            ans.add(i + 1);
        }
        return ans;
    }
}
```