# LeetCode 656: Coin Path

## Problem Restatement

We are given an integer array `coins` and an integer `maxJump`.

The array represents positions from `1` to `n`.

At position `i`, we must pay `coins[i]` coins when we visit that position.

Some positions have value `-1`. These positions are blocked and cannot be visited.

We start at position `1`.

We want to reach position `n`.

From position `i`, we may jump forward to any position from:

```text
i + 1
```

up to:

```text
i + maxJump
```

Return the path of positions we visit, using 1-based indices.

The path must have minimum total cost. If multiple paths have the same minimum cost, return the lexicographically smallest path. If reaching position `n` is impossible, return an empty list.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An array `coins` and an integer `maxJump` |
| Output | A list of 1-based indices in the chosen path |
| Start | Position `1` |
| Target | Position `n` |
| Blocked position | A position where `coins[i] == -1` |
| Jump rule | From position `i`, jump at most `maxJump` steps forward |
| Tie-breaking | Return the lexicographically smallest path among minimum-cost paths |

Example function shape:

```python
def cheapestJump(coins: list[int], maxJump: int) -> list[int]:
    ...
```

## Examples

Consider:

```python
coins = [1, 2, 4, -1, 2]
maxJump = 2
```

The positions are:

| Position | Cost |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | blocked |
| 5 | 2 |

From position `1`, we can jump to position `2` or `3`.

One valid path is:

```python
[1, 3, 5]
```

Its cost is:

```text
1 + 4 + 2 = 7
```

Position `4` is blocked, so paths through position `4` are invalid.

The answer is:

```python
[1, 3, 5]
```

Now consider:

```python
coins = [1, 2, 4, -1, 2]
maxJump = 1
```

We can only move one step at a time.

The path would need to go through position `4`, but position `4` is blocked.

So the answer is:

```python
[]
```

## First Thought: Try Every Path

A direct solution is to try every possible jump sequence from position `1`.

At each position, we can jump to up to `maxJump` next positions.

This creates a branching search tree.

For each path, we compute the total cost. Then we choose the path with the smallest cost. If there is a tie, we choose the lexicographically smallest path.

This is logically correct, but it repeats the same subproblems many times.

For example, many different paths may reach the same position. Once we are at that position, the best way to finish is the same regardless of how we got there.

That repeated structure suggests dynamic programming.

## Key Insight

Let `dp[i]` mean:

```text
minimum cost needed to reach the final position starting from index i
```

Here, `i` is a 0-based index into `coins`.

If `coins[i] == -1`, then position `i` is blocked, so `dp[i]` is impossible.

If `i` is the last index, then:

```python
dp[i] = coins[i]
```

because we are already at the destination and only pay the current position cost.

For every other index, we try all next reachable positions:

```text
i + 1, i + 2, ..., i + maxJump
```

and choose the one with minimum total cost.

The recurrence is:

```text
dp[i] = coins[i] + min(dp[j])
```

where `j` ranges over reachable next indices.

## Lexicographic Tie-Breaking

The problem also asks for the lexicographically smallest path among all minimum-cost paths.

A path is lexicographically smaller if, at the first different index, it has the smaller position number.

Since we reconstruct the path from left to right, we can enforce this rule by choosing the smallest next index that still gives the optimal cost.

That means when we compute `dp[i]`, if two next positions give the same cost, we prefer the smaller next position.

So we scan next positions in increasing order and update only when we find a strictly smaller cost.

This preserves the earliest possible next position for ties.

## Algorithm

Use bottom-up dynamic programming from right to left.

Create:

| Array | Meaning |
|---|---|
| `dp` | Minimum cost from index `i` to the end |
| `next_index` | The next index to jump to from `i` on the best path |

Initialize:

```python
dp[n - 1] = coins[n - 1]
```

Then process indices from `n - 2` down to `0`.

For each index `i`:

1. If `coins[i] == -1`, skip it.
2. Try every `j` from `i + 1` to `min(i + maxJump, n - 1)`.
3. Ignore `j` if `dp[j]` is impossible.
4. Compute `cost = coins[i] + dp[j]`.
5. If `cost` is smaller than `dp[i]`, update `dp[i]` and `next_index[i]`.
6. Do not update on equal cost, because the earlier `j` is lexicographically better.

After filling DP:

1. If `dp[0]` is impossible, return `[]`.
2. Otherwise, follow `next_index` from `0` to `n - 1`.
3. Convert each index to 1-based form.

## Correctness

The value `dp[i]` represents the minimum cost to reach the last position starting from index `i`.

For the last index, this is exactly `coins[i]`, because we are already at the destination.

For every other usable index `i`, any valid path must jump next to some index `j` within `maxJump` steps. After that jump, the best possible remaining cost is `dp[j]`. Therefore, the best cost from `i` is `coins[i] + min(dp[j])` over all valid next positions.

The algorithm computes states from right to left, so when it computes `dp[i]`, every reachable `dp[j]` has already been computed.

The `next_index` array stores a next position that achieves the minimum cost. Since candidates are checked from smaller index to larger index and equal-cost updates are ignored, the stored next position is the smallest possible next index among all optimal choices.

During reconstruction, the algorithm repeatedly chooses the smallest next index that can still lead to an optimal path. Therefore, among all minimum-cost paths, the constructed path is lexicographically smallest.

If `dp[0]` remains impossible, no valid sequence of jumps can reach the last position from the start, so returning an empty list is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * maxJump)` | For each index, we check up to `maxJump` next positions |
| Space | `O(n)` | We store `dp` and `next_index` |

## Implementation

```python
from math import inf
from typing import List

class Solution:
    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:
        n = len(coins)

        if n == 0 or coins[0] == -1 or coins[-1] == -1:
            return []

        dp = [inf] * n
        next_index = [-1] * n

        dp[n - 1] = coins[n - 1]

        for i in range(n - 2, -1, -1):
            if coins[i] == -1:
                continue

            limit = min(n - 1, i + maxJump)

            for j in range(i + 1, limit + 1):
                if dp[j] == inf:
                    continue

                cost = coins[i] + dp[j]

                if cost < dp[i]:
                    dp[i] = cost
                    next_index[i] = j

        if dp[0] == inf:
            return []

        path = []
        i = 0

        while i != -1:
            path.append(i + 1)

            if i == n - 1:
                break

            i = next_index[i]

        return path
```

## Code Explanation

We first reject impossible start or end positions:

```python
if n == 0 or coins[0] == -1 or coins[-1] == -1:
    return []
```

Then we create the DP arrays:

```python
dp = [inf] * n
next_index = [-1] * n
```

`inf` means the end cannot be reached from that index yet.

The destination cost is initialized directly:

```python
dp[n - 1] = coins[n - 1]
```

Then we process from right to left:

```python
for i in range(n - 2, -1, -1):
```

Blocked positions are skipped:

```python
if coins[i] == -1:
    continue
```

For a valid position, we try all jumps within range:

```python
limit = min(n - 1, i + maxJump)

for j in range(i + 1, limit + 1):
```

If `j` cannot reach the end, we ignore it:

```python
if dp[j] == inf:
    continue
```

Otherwise, we compute the total cost through `j`:

```python
cost = coins[i] + dp[j]
```

We update only on strictly smaller cost:

```python
if cost < dp[i]:
    dp[i] = cost
    next_index[i] = j
```

This is important for lexicographic order. Since `j` is scanned from left to right, the first minimum-cost `j` is the smallest valid next position.

After DP finishes, we check whether index `0` can reach the end:

```python
if dp[0] == inf:
    return []
```

Finally, we reconstruct the path:

```python
path = []
i = 0

while i != -1:
    path.append(i + 1)

    if i == n - 1:
        break

    i = next_index[i]
```

We append `i + 1` because the problem asks for 1-based indices.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.cheapestJump([1, 2, 4, -1, 2], 2) == [1, 3, 5]
    assert s.cheapestJump([1, 2, 4, -1, 2], 1) == []

    # Direct jump is possible and cheapest.
    assert s.cheapestJump([1, 10, 10, 1], 3) == [1, 4]

    # Tie on total cost. Choose lexicographically smaller path.
    assert s.cheapestJump([1, 1, 1, 1], 2) == [1, 2, 4]

    # Blocked cells force a longer route.
    assert s.cheapestJump([1, -1, 2, 2, 1], 2) == [1, 3, 5]

    # Destination blocked.
    assert s.cheapestJump([1, 2, -1], 2) == []

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,4,-1,2]`, `maxJump = 2` | Standard reachable case |
| `[1,2,4,-1,2]`, `maxJump = 1` | Blocked cell makes destination unreachable |
| Direct jump | Confirms large jumps are allowed |
| Equal-cost paths | Confirms lexicographic tie-breaking |
| Forced route around blocked cells | Confirms `-1` handling |
| Blocked destination | Confirms impossible target handling |