# LeetCode 403: Frog Jump

## Problem Restatement

A frog wants to cross a river by jumping on stones.

The stones are given as a sorted array:

```python
stones
```

Each value in `stones` is a position on the river.

The frog starts on the first stone, which is always position `0`.

The first jump must be exactly `1` unit.

After that, if the frog’s previous jump was `k` units, then the next jump must be one of:

```python
k - 1
k
k + 1
```

The frog can only jump forward, and it can land only on stones.

Return `True` if the frog can reach the last stone. Otherwise, return `False`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted list of stone positions |
| Output | `True` if the frog can reach the last stone, otherwise `False` |
| Start | The frog starts at `stones[0]`, which is `0` |
| First jump | Must be exactly `1` |
| Next jumps | If the last jump was `k`, the next jump may be `k - 1`, `k`, or `k + 1` |
| Direction | Forward only |
| Landing rule | The frog must land on a stone |

Constraints include `2 <= stones.length <= 2000`, `stones[0] == 0`, and the stones are strictly increasing. The problem statement specifies the first jump rule and the `k - 1`, `k`, `k + 1` transition rule.

## Examples

Consider:

```python
stones = [0, 1, 3, 5, 6, 8, 12, 17]
```

The answer is:

```python
True
```

One valid path is:

```python
0 -> 1 -> 3 -> 5 -> 8 -> 12 -> 17
```

The jump lengths are:

```python
1, 2, 2, 3, 4, 5
```

Each jump follows the rule. After a jump of `2`, the next jump can be `1`, `2`, or `3`. After a jump of `3`, the next jump can be `2`, `3`, or `4`.

Now consider:

```python
stones = [0, 1, 2, 3, 4, 8, 9, 11]
```

The answer is:

```python
False
```

The frog can reach stone `4`, but the next stone is `8`. The gap is too large for the jump sizes available at that point. This matches the standard example for the problem.

## First Thought: Backtracking

A direct way is to try every possible jump.

From a stone, if the previous jump was `k`, recursively try:

```python
k - 1
k
k + 1
```

If one of those jumps lands on another stone, continue from there.

This matches the problem naturally.

The state is:

```python
current stone position
last jump length
```

But plain recursion repeats many states.

For example, the frog may reach the same stone with the same previous jump through different paths. Once that state has been solved, solving it again wastes time.

So we add memoization.

## Key Insight

The frog’s future depends only on two values:

```python
stone index
last jump length
```

It does not matter how the frog reached that state.

If the frog is on stone `i` and the previous jump was `k`, then the possible next jumps are fully determined:

```python
k - 1, k, k + 1
```

So we can define a dynamic programming state:

```python
dfs(i, k)
```

Meaning:

Can the frog reach the last stone if it is currently on stone `i` and its previous jump length was `k`?

To quickly check whether a target landing position exists, store all stone positions in a hash map:

```python
position -> index
```

## Algorithm

Create a dictionary `pos` mapping each stone position to its index.

Then define a memoized DFS:

```python
dfs(i, k)
```

where:

| Value | Meaning |
|---|---|
| `i` | Current stone index |
| `k` | Previous jump length |

For each state:

1. If `i` is the last stone index, return `True`.
2. Try next jump lengths `k - 1`, `k`, and `k + 1`.
3. Ignore non-positive jump lengths.
4. Let the next stone position be `stones[i] + jump`.
5. If that position exists, recursively test that next state.
6. If any recursive call returns `True`, return `True`.
7. Otherwise, return `False`.

The first call is:

```python
dfs(0, 0)
```

This works because the first valid next jump from `0` is `1`.

From `k = 0`, the possible next jumps are:

```python
-1, 0, 1
```

Only `1` is positive, so the first jump rule is enforced naturally.

## Correctness

We prove that `dfs(i, k)` returns `True` exactly when the frog can reach the last stone from stone `i` after making a previous jump of length `k`.

If `i` is the last stone index, the frog has already reached the goal, so `dfs(i, k)` correctly returns `True`.

Otherwise, the frog’s next jump must be one of `k - 1`, `k`, or `k + 1`. The algorithm checks exactly these three jump lengths. It rejects non-positive jumps because the frog can only move forward.

For each valid jump length, the algorithm computes the landing position. If that position exists in the stone map, then the jump is legal. The recursive call tests whether the frog can reach the last stone after making that jump.

If any legal next jump can eventually reach the last stone, the algorithm returns `True`.

If none of the legal next jumps can reach the last stone, then every possible move from this state fails, so the algorithm returns `False`.

Memoization only stores already computed results for the same `(i, k)` state. Since the answer for a state depends only on `i` and `k`, memoization does not change correctness.

Therefore, the initial call returns `True` exactly when the frog can cross the river.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | There are at most `O(n^2)` reachable `(stone, jump)` states |
| Space | `O(n^2)` | Memoization may store many `(index, jump)` states |

Here `n` is the number of stones.

The number of stones is at most `2000`, so an `O(n^2)` dynamic programming solution is acceptable.

## Implementation

```python
from functools import cache
from typing import List

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        pos = {stone: i for i, stone in enumerate(stones)}
        n = len(stones)

        @cache
        def dfs(i: int, k: int) -> bool:
            if i == n - 1:
                return True

            for jump in (k - 1, k, k + 1):
                if jump <= 0:
                    continue

                next_pos = stones[i] + jump

                if next_pos in pos:
                    if dfs(pos[next_pos], jump):
                        return True

            return False

        return dfs(0, 0)
```

## Code Explanation

We first build a fast lookup table:

```python
pos = {stone: i for i, stone in enumerate(stones)}
```

This lets us check whether a landing position is a stone in expected constant time.

Then we define:

```python
dfs(i, k)
```

This means the frog is currently on `stones[i]`, and the previous jump length was `k`.

The base case is:

```python
if i == n - 1:
    return True
```

If the frog is on the last stone, it has crossed the river.

Then we try the three allowed next jump lengths:

```python
for jump in (k - 1, k, k + 1):
```

We skip invalid jumps:

```python
if jump <= 0:
    continue
```

Then we compute the next landing position:

```python
next_pos = stones[i] + jump
```

If that position is a stone, we recurse:

```python
if next_pos in pos:
    if dfs(pos[next_pos], jump):
        return True
```

If none of the possible jumps works, this state fails:

```python
return False
```

Finally, we start at stone `0` with previous jump length `0`:

```python
return dfs(0, 0)
```

## Testing

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

    assert s.canCross([0, 1, 3, 5, 6, 8, 12, 17]) is True
    assert s.canCross([0, 1, 2, 3, 4, 8, 9, 11]) is False
    assert s.canCross([0, 1]) is True
    assert s.canCross([0, 2]) is False
    assert s.canCross([0, 1, 2]) is True
    assert s.canCross([0, 1, 3, 6, 10, 15, 21]) is True
    assert s.canCross([0, 1, 3, 6, 10, 13, 15, 18]) is True

    print("all tests passed")
```

## Test Notes

| Test | Why |
|---|---|
| `[0, 1, 3, 5, 6, 8, 12, 17]` | Standard reachable case |
| `[0, 1, 2, 3, 4, 8, 9, 11]` | Standard unreachable case |
| `[0, 1]` | Minimum successful input |
| `[0, 2]` | First jump must be exactly `1` |
| `[0, 1, 2]` | Small case with repeated jump length `1` |
| `[0, 1, 3, 6, 10, 15, 21]` | Increasing jump sequence |
| `[0, 1, 3, 6, 10, 13, 15, 18]` | Requires choosing smaller later jumps |