# LeetCode 741: Cherry Pickup

## Problem Restatement

We are given an `n x n` grid.

Each cell contains one of three values:

| Value | Meaning |
|---:|---|
| `1` | A cell with one cherry |
| `0` | An empty cell |
| `-1` | A thorn cell that cannot be passed |

We start at the top-left cell:

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

We need to travel to the bottom-right cell:

```python
(n - 1, n - 1)
```

using only:

```text
right
down
```

Then we return from the bottom-right cell to the top-left cell using only:

```text
left
up
```

Whenever we pass through a cell with a cherry, we collect it. After a cherry is collected, that cell becomes empty. A cherry can be collected at most once.

Return the maximum number of cherries we can collect. If there is no valid round trip, return `0`.

The official constraints include `1 <= n <= 50`, `grid[i][j]` is `-1`, `0`, or `1`, and the start and end cells are not thorns.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An `n x n` integer grid |
| Output | Maximum number of cherries collectible |
| Valid forward moves | Right or down |
| Valid return moves | Left or up |
| Blocked cell | `-1` |
| Cherry rule | A cherry can be collected once |

Example function shape:

```python
def cherryPickup(grid: list[list[int]]) -> int:
    ...
```

## Examples

### Example 1

```python
grid = [
    [0, 1, -1],
    [1, 0, -1],
    [1, 1,  1],
]
```

One optimal path goes down, down, right, right to reach the end.

Then the return path collects one remaining cherry.

The maximum total is:

```python
5
```

So the answer is:

```python
5
```

### Example 2

```python
grid = [
    [1, 1, -1],
    [1, -1, 1],
    [-1, 1, 1],
]
```

There is no valid way to complete the trip from start to end and back.

The answer is:

```python
0
```

## First Thought: Pick One Path, Then Pick Return Path

A tempting approach is:

1. Find a path from start to end that collects many cherries.
2. Remove those cherries.
3. Find the best return path.

This does not work.

The best first path may block the best total round trip. Sometimes we should collect fewer cherries on the way down so the return path can collect more.

So the two paths must be optimized together, not separately.

## Key Insight

The return path from bottom-right to top-left using `left` and `up` can be reversed.

After reversing, it becomes another path from top-left to bottom-right using `right` and `down`.

So the whole round trip can be seen as:

```text
two people start at (0, 0)
both move to (n - 1, n - 1)
each step is either right or down
```

Both people move at the same time.

If both people land on the same cell, we count its cherry once.

This converts the problem into a dynamic programming problem over two simultaneous paths. This is the standard formulation for this problem.

## Algorithm

Let:

```python
dp[k][r1][r2]
```

mean the maximum cherries collected after both people have taken exactly `k` steps.

At step `k`:

```python
person 1 is at (r1, c1)
person 2 is at (r2, c2)
```

Since each person has taken `k` total moves:

```python
c1 = k - r1
c2 = k - r2
```

So we only need `k`, `r1`, and `r2`.

For each state:

1. Skip it if either position is outside the grid.
2. Skip it if either position is a thorn.
3. Try the four possible previous states:
   - both came from above
   - person 1 from above, person 2 from left
   - person 1 from left, person 2 from above
   - both came from left
4. Add cherries from the current cells.
5. If both people are on the same cell, add the cherry once.

The answer is:

```python
max(0, dp[2 * n - 2][n - 1][n - 1])
```

We use `max(0, ...)` because unreachable states are stored as negative infinity.

## Correctness

Reversing the return trip transforms it into a second forward trip from `(0, 0)` to `(n - 1, n - 1)`. Therefore every valid round trip corresponds to two simultaneous forward paths, and every pair of forward paths corresponds to one round trip.

At step `k`, both paths have made the same number of moves. If one path is at row `r`, its column is forced to be `k - r`. Therefore the state `dp[k][r1][r2]` fully describes both positions.

The transition checks all possible previous moves for both paths. Since each person can only move right or down, their previous cell must have been either above or left. The four previous-state combinations cover all valid ways to arrive at the current pair of cells.

The value added at each state is exactly the number of new cherries collected at the two current positions. If the two people stand on different cells, both cherries may be counted. If they stand on the same cell, the cherry is counted once, matching the rule that each cherry can be collected only once.

The DP processes steps in increasing order, so every previous state is already computed before it is used.

Thus the final state gives the maximum cherries over all valid pairs of paths. If the final state is unreachable, the correct answer is `0`.

## Complexity

Let `n` be the grid size.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^3)` | There are `O(n)` steps and `O(n^2)` row pairs per step |
| Space | `O(n^3)` | The full DP table stores every step and row pair |

This can be optimized to `O(n^2)` space by keeping only the previous step, but the full DP version is easier to read.

## Implementation

```python
class Solution:
    def cherryPickup(self, grid: list[list[int]]) -> int:
        n = len(grid)
        neg_inf = float("-inf")

        steps = 2 * n - 1
        dp = [
            [[neg_inf] * n for _ in range(n)]
            for _ in range(steps)
        ]

        dp[0][0][0] = grid[0][0]

        for k in range(1, steps):
            for r1 in range(n):
                for r2 in range(n):
                    c1 = k - r1
                    c2 = k - r2

                    if c1 < 0 or c1 >= n:
                        continue

                    if c2 < 0 or c2 >= n:
                        continue

                    if grid[r1][c1] == -1:
                        continue

                    if grid[r2][c2] == -1:
                        continue

                    best_prev = neg_inf

                    for prev_r1 in (r1, r1 - 1):
                        for prev_r2 in (r2, r2 - 1):
                            if prev_r1 < 0 or prev_r2 < 0:
                                continue

                            best_prev = max(
                                best_prev,
                                dp[k - 1][prev_r1][prev_r2],
                            )

                    if best_prev == neg_inf:
                        continue

                    cherries = grid[r1][c1]

                    if r1 != r2 or c1 != c2:
                        cherries += grid[r2][c2]

                    dp[k][r1][r2] = best_prev + cherries

        return max(0, dp[steps - 1][n - 1][n - 1])
```

## Code Explanation

We use `neg_inf` for impossible states:

```python
neg_inf = float("-inf")
```

The number of simultaneous steps from `(0, 0)` to `(n - 1, n - 1)` is:

```python
steps = 2 * n - 1
```

That includes step `0`.

The start state is:

```python
dp[0][0][0] = grid[0][0]
```

At each step, columns are derived from rows:

```python
c1 = k - r1
c2 = k - r2
```

If either column is outside the grid, the state is impossible.

If either cell is a thorn, the state is impossible:

```python
if grid[r1][c1] == -1:
    continue

if grid[r2][c2] == -1:
    continue
```

For each current row, the previous row was either the same row or one row above:

```python
for prev_r1 in (r1, r1 - 1):
    for prev_r2 in (r2, r2 - 1):
```

Same row means the person came from the left.

One row above means the person came from above.

Then we count cherries:

```python
cherries = grid[r1][c1]
```

If the two people are on different cells, add both cells:

```python
if r1 != r2 or c1 != c2:
    cherries += grid[r2][c2]
```

Finally, return the best valid result, or `0` if no valid path exists.

## Testing

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

    assert s.cherryPickup([
        [0, 1, -1],
        [1, 0, -1],
        [1, 1,  1],
    ]) == 5

    assert s.cherryPickup([
        [1, 1, -1],
        [1, -1, 1],
        [-1, 1, 1],
    ]) == 0

    assert s.cherryPickup([[0]]) == 0
    assert s.cherryPickup([[1]]) == 1

    assert s.cherryPickup([
        [1, 1],
        [1, 1],
    ]) == 4

    assert s.cherryPickup([
        [0, 1, 1],
        [1, -1, 1],
        [1, 1, 1],
    ]) == 7

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | Checks round-trip maximum |
| Blocked grid | No valid complete route |
| `[[0]]` | Single empty start/end cell |
| `[[1]]` | Single cherry counted once |
| Full `2 x 2` grid | All cherries can be collected |
| Grid with center thorn | Paths must route around obstacle |