LeetCode Problem 741

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Cherry Pickup - LeetCode 741

Problem Understanding

This problem asks us to collect the maximum possible number of cherries while making two trips across a square grid.

The first trip starts at the top left corner (0, 0) and moves to the bottom right corner (n - 1, n - 1) using only right or down moves. After reaching the destination, we must return to the starting point using only left or up moves.

The grid contains three kinds of cells:

• 0 means the cell is empty and can be traversed.
• 1 means the cell contains a cherry that can be collected.
• -1 means the cell contains a thorn and cannot be traversed.

When a cherry is picked up once, it disappears from the grid. This means the same cherry cannot be collected twice.

The goal is to compute the maximum total number of cherries that can be collected across both trips combined. If no valid path exists from the start to the destination, the answer must be 0.

At first glance, this looks like a pathfinding problem with two separate traversals. However, independently optimizing the forward and backward trips does not work because the choice made during the first trip changes the state of the grid for the second trip.

The constraints are important:

• n can be as large as 50
• The grid has up to 2500 cells

A naive exhaustive search would be far too expensive because the number of possible paths grows exponentially.

Several edge cases are important:

• The destination may be unreachable because of thorns.
• The start or destination cell may contain a cherry.
• Both trips may overlap heavily.
• Multiple optimal paths may share cells.
• We must avoid double counting cherries when two traversals visit the same cell.

The most important conceptual insight is that the forward and backward trips can be transformed into two people walking from (0, 0) to (n - 1, n - 1) simultaneously.

Approaches

Brute Force Approach

The brute force solution tries every possible path from the start to the destination, then for each such path, modifies the grid and tries every possible return path.

A path from (0, 0) to (n - 1, n - 1) contains exactly 2n - 2 moves, and each move has two choices, either right or down. This creates an exponential number of possible paths.

For every forward path, we would need to:

1. Simulate collecting cherries.
2. Modify the grid.
3. Explore every valid return path.
4. Track the maximum total cherries.

This approach is correct because it checks all possible combinations of forward and backward journeys. However, it becomes computationally infeasible very quickly.

For n = 50, the number of paths is astronomically large.

Key Insight for the Optimal Solution

The major insight is that the forward trip and backward trip can be modeled as two people walking from the start to the destination at the same time.

Why does this work?

• The forward journey uses only right and down moves.
• The return journey uses only left and up moves.
• If we reverse the return trip, it also becomes a path from the start to the destination using right and down moves.

Now we can think of the problem as:

Two travelers start at (0,0) and both move toward (n-1,n-1) simultaneously.

At every step:

• Each traveler moves either right or down.
• Both travelers take the same number of total steps.
• If both land on the same cell, we count the cherry only once.

This transformation removes the complicated "modify the grid between trips" issue.

The state becomes:

• Position of traveler 1: (r1, c1)
• Position of traveler 2: (r2, c2)

Since both travelers have taken the same number of steps:

r1 + c1 = r2 + c2

This allows us to derive one coordinate from the others and reduce the DP state dimension.

We then use dynamic programming with memoization to compute the maximum cherries collectible from each state.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates all forward and backward paths
Optimal Dynamic Programming	O(n³)	O(n³)	Uses simultaneous traversal with memoization

Algorithm Walkthrough

Step 1: Reframe the Problem

Instead of thinking about one person going forward and backward, think of two people starting at (0,0) and moving toward (n-1,n-1) simultaneously.

Each move increases the total number of steps by one.

Step 2: Define the DP State

Let:

dp(r1, c1, r2)

represent the maximum cherries collectible when:

• Traveler 1 is at (r1, c1)
• Traveler 2 is at (r2, c2)

Since both travelers took the same number of steps:

r1 + c1 = r2 + c2

we can compute:

c2 = r1 + c1 - r2

This reduces the state space from 4 dimensions to 3 dimensions.

Step 3: Handle Invalid States

A state is invalid if:

• Any coordinate goes outside the grid
• Either traveler lands on a thorn cell

For invalid states, return negative infinity so they are never chosen in the maximum calculation.

Step 4: Handle the Destination

If both travelers reach (n-1, n-1), return the value of that cell.

This is the base case.

Step 5: Collect Cherries

At each state:

• Add the cherry at traveler 1's position
• Add the cherry at traveler 2's position
• If both travelers are on the same cell, count it only once

Step 6: Explore the Four Possible Move Combinations

Each traveler can move either right or down.

This creates four combinations:

1. Down, Down
2. Down, Right
3. Right, Down
4. Right, Right

Take the maximum result among these recursive calls.

Step 7: Memoize Results

Many states repeat during recursion.

Use memoization to cache results for each state so each state is computed only once.

Step 8: Return the Final Answer

The recursion may return a negative value if no valid path exists.

In that case, return 0.

Otherwise, return the computed maximum.

Why it works

The algorithm works because every valid forward and backward trip pair corresponds exactly to two simultaneous forward traversals. The DP state fully captures the positions of both travelers after the same number of steps. By exploring all move combinations and memoizing results, the algorithm guarantees that every valid pair of paths is considered exactly once. Counting shared cells only once correctly models the cherry removal behavior.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)

        @lru_cache(None)
        def dp(r1: int, c1: int, r2: int) -> int:
            c2 = r1 + c1 - r2

            # Out of bounds
            if (
                r1 >= n or c1 >= n or
                r2 >= n or c2 >= n
            ):
                return float('-inf')

            # Thorn cell
            if (
                grid[r1][c1] == -1 or
                grid[r2][c2] == -1
            ):
                return float('-inf')

            # Reached destination
            if r1 == n - 1 and c1 == n - 1:
                return grid[r1][c1]

            cherries = grid[r1][c1]

            # Avoid double counting
            if (r1, c1) != (r2, c2):
                cherries += grid[r2][c2]

            best_next = max(
                dp(r1 + 1, c1, r2 + 1),  # down, down
                dp(r1 + 1, c1, r2),      # down, right
                dp(r1, c1 + 1, r2 + 1),  # right, down
                dp(r1, c1 + 1, r2)       # right, right
            )

            cherries += best_next

            return cherries

        result = dp(0, 0, 0)

        return max(0, result)

The implementation starts by defining a memoized recursive function dp.

The state uses three coordinates because the fourth coordinate can be derived from the total number of steps taken. This significantly reduces the state space.

The first section of the function checks whether the state is valid. If either traveler goes out of bounds or lands on a thorn, the state is impossible and returns negative infinity.

The base case occurs when traveler 1 reaches the destination. Since both travelers always take the same number of steps, traveler 2 must also be there.

The code then collects cherries from both positions. If both travelers occupy the same cell, the cherry is counted only once.

Next, the algorithm recursively explores all four move combinations and selects the maximum future value.

Finally, the function returns the current cherries plus the best future result.

The outer function starts the recursion at (0,0) for both travelers and ensures that negative results become 0.

Go Solution

package main

import "math"

func cherryPickup(grid [][]int) int {
	n := len(grid)

	type State struct {
		r1 int
		c1 int
		r2 int
	}

	memo := make(map[State]int)

	var dp func(int, int, int) int

	dp = func(r1, c1, r2 int) int {
		c2 := r1 + c1 - r2

		// Out of bounds
		if r1 >= n || c1 >= n || r2 >= n || c2 >= n {
			return math.MinInt32
		}

		// Thorn cells
		if grid[r1][c1] == -1 || grid[r2][c2] == -1 {
			return math.MinInt32
		}

		// Destination
		if r1 == n-1 && c1 == n-1 {
			return grid[r1][c1]
		}

		state := State{r1, c1, r2}

		if val, exists := memo[state]; exists {
			return val
		}

		cherries := grid[r1][c1]

		// Avoid double counting
		if r1 != r2 || c1 != c2 {
			cherries += grid[r2][c2]
		}

		bestNext := max(
			dp(r1+1, c1, r2+1),
			dp(r1+1, c1, r2),
			dp(r1, c1+1, r2+1),
			dp(r1, c1+1, r2),
		)

		cherries += bestNext

		memo[state] = cherries

		return cherries
	}

	result := dp(0, 0, 0)

	if result < 0 {
		return 0
	}

	return result
}

func max(values ...int) int {
	best := values[0]

	for _, v := range values {
		if v > best {
			best = v
		}
	}

	return best
}

The Go implementation follows the same algorithmic structure as the Python solution. Since Go does not provide built in memoization decorators like Python's lru_cache, we explicitly maintain a hash map keyed by a custom State struct.

Negative infinity is represented using math.MinInt32.

Go slices are reference types, so the grid is efficiently passed without copying.

Worked Examples

Example 1

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

Initial State

Both travelers start at (0,0).

Traveler 1	Traveler 2	Cherries
(0,0)	(0,0)	0

Step 1

Possible moves:

• Down / Down
• Down / Right
• Right / Down
• Right / Right

The optimal choice eventually becomes:

• Traveler 1: Down
• Traveler 2: Right

Traveler 1	Traveler 2	Collected
(1,0)	(0,1)	2

Step 2

Next optimal move:

Traveler 1	Traveler 2	Collected
(2,0)	(1,1)	3

Step 3

Next optimal move:

Traveler 1	Traveler 2	Collected
(2,1)	(2,1)	4

The shared cell counts only once.

Step 4

Final destination:

Traveler 1	Traveler 2	Collected
(2,2)	(2,2)	5

Final answer:

5

Example 2

grid = [
  [1,1,-1],
  [1,-1,1],
  [-1,1,1]
]

The travelers eventually encounter unavoidable thorn cells.

No valid path exists from the start to the destination.

The DP recursion returns negative infinity, and the final answer becomes:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n³)	There are O(n³) unique DP states, each processed once
Space	O(n³)	Memoization stores O(n³) states

The state space consists of three independent variables:

• r1
• c1
• r2

Each ranges from 0 to n-1.

The fourth coordinate is derived mathematically, which reduces complexity from O(n⁴) to O(n³).

Each state computes four transitions in constant time, so the total runtime remains O(n³).

Test Cases

from typing import List
from functools import lru_cache

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)

        @lru_cache(None)
        def dp(r1: int, c1: int, r2: int) -> int:
            c2 = r1 + c1 - r2

            if (
                r1 >= n or c1 >= n or
                r2 >= n or c2 >= n
            ):
                return float('-inf')

            if (
                grid[r1][c1] == -1 or
                grid[r2][c2] == -1
            ):
                return float('-inf')

            if r1 == n - 1 and c1 == n - 1:
                return grid[r1][c1]

            cherries = grid[r1][c1]

            if (r1, c1) != (r2, c2):
                cherries += grid[r2][c2]

            cherries += max(
                dp(r1 + 1, c1, r2 + 1),
                dp(r1 + 1, c1, r2),
                dp(r1, c1 + 1, r2 + 1),
                dp(r1, c1 + 1, r2)
            )

            return cherries

        return max(0, dp(0, 0, 0))

solver = Solution()

assert solver.cherryPickup([
    [0,1,-1],
    [1,0,-1],
    [1,1,1]
]) == 5  # provided example

assert solver.cherryPickup([
    [1,1,-1],
    [1,-1,1],
    [-1,1,1]
]) == 0  # no valid path

assert solver.cherryPickup([
    [1]
]) == 1  # single cell with cherry

assert solver.cherryPickup([
    [0]
]) == 0  # single empty cell

assert solver.cherryPickup([
    [1,1],
    [1,1]
]) == 4  # all cherries collected

assert solver.cherryPickup([
    [1,-1],
    [-1,1]
]) == 0  # completely blocked

assert solver.cherryPickup([
    [0,1,1],
    [1,1,1],
    [1,1,0]
]) == 7  # many overlapping optimal paths

assert solver.cherryPickup([
    [1,1,1],
    [1,-1,1],
    [1,1,1]
]) == 8  # must avoid thorn while maximizing cherries

Test Summary

Test	Why
[[0,1,-1],[1,0,-1],[1,1,1]]	Validates standard example
[[1,1,-1],[1,-1,1],[-1,1,1]]	Validates unreachable destination
[[1]]	Smallest possible grid with cherry
[[0]]	Smallest possible empty grid
[[1,1],[1,1]]	Ensures all cherries are counted correctly
[[1,-1],[-1,1]]	Tests fully blocked traversal
Dense cherry grid	Tests overlap handling
Grid with central thorn	Tests path rerouting

Edge Cases

Completely Blocked Paths

A grid may contain thorn placements that make reaching the destination impossible. A naive implementation might still attempt to compute partial paths or accidentally return negative values.

This implementation handles blocked paths by returning negative infinity for invalid states. If all possible transitions are invalid, the final answer becomes negative, and the outer function converts it to 0.

Both Travelers on the Same Cell

During simultaneous traversal, both travelers may land on the same cell at the same time. Without careful handling, the algorithm would count the cherry twice.

The implementation explicitly checks:

if (r1, c1) != (r2, c2):

This guarantees that shared cells contribute only once.

Single Cell Grid

When n = 1, the start and destination are the same cell. A naive recursive solution may mishandle this because no movement occurs.

The base case immediately returns the cell value when the destination is reached, which correctly handles single cell inputs.

Heavy Path Overlap

Sometimes the optimal strategy requires both traversals to reuse many of the same cells. Greedy approaches that try to maximize the first trip independently often fail here.

The simultaneous traversal DP naturally models overlap correctly because both travelers are optimized together rather than independently.