You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.
0 means the cell is empty, so you can pass through,1 means the cell contains a cherry that you can pick up and pass through, or-1 means the cell contains a thorn that blocks your way.Return the maximum number of cherries you can collect by following the rules below:
(0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1).(n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells.0.(0, 0) and (n - 1, n - 1), then no cherries can be collected.
Example 1:
Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]] Output: 5 Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2). 4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]]. Then, the player went left, up, up, left to return home, picking up one more cherry. The total number of cherries picked up is 5, and this is the maximum possible.
Example 2:
Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]] Output: 0
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 50grid[i][j] is -1, 0, or 1.grid[0][0] != -1grid[n - 1][n - 1] != -1Problem Overview: You are given an n x n grid where cells contain cherries (1), empty spaces (0), or thorns (-1). Starting at (0,0), you must reach (n-1,n-1) and then return to the start. Each cherry can only be collected once and cells with -1 cannot be visited. The goal is to maximize the total cherries collected across both trips.
A direct simulation of going forward and then returning leads to complicated state management. The key insight is that the forward and backward trips can be modeled as two people walking from the start to the end at the same time. Both take the same number of steps k, and their positions determine which cherries are collected.
Approach 1: Dynamic Programming with 3D DP Table (Time: O(n^3), Space: O(n^3))
This approach models the two simultaneous walkers using dynamic programming. Let dp[k][i1][i2] represent the maximum cherries collected after k steps when the first person is at (i1, j1) and the second at (i2, j2). Because both walkers take the same number of steps, j1 = k - i1 and j2 = k - i2. For each step, evaluate four possible transitions: both move right, both move down, or one moves right while the other moves down. If either position hits a thorn, the state is invalid. When both walkers land on the same cell, count the cherry only once.
The DP iterates over steps from 0 to 2n-2, computing the best value from previous states. This transforms the round-trip path problem into a single synchronized traversal problem. The algorithm uses dynamic programming across a matrix grid, tracking all valid combinations of row positions.
Approach 2: Dynamic Programming with Space Optimization (Time: O(n^3), Space: O(n^2))
The 3D DP table stores states for every step, but only the previous step is needed to compute the next one. Replace the full dp[k][i1][i2] structure with two 2D arrays: one for the current step and one for the previous step. During each iteration over k, update the new matrix using values from the previous matrix and then swap references.
This reduces memory from O(n^3) to O(n^2) while keeping the same transitions and logic. The time complexity remains cubic because you still iterate through all valid combinations of i1 and i2 for each step. This version is typically preferred in production code or memory-constrained environments. The technique is common in array and DP problems where state transitions depend only on the previous iteration.
Recommended for interviews: Interviewers usually expect the 3D DP formulation because it demonstrates the key insight of converting the round trip into two synchronized paths. Explaining the state definition and transitions clearly shows strong dynamic programming skills. Implementing the space-optimized version afterward highlights deeper understanding of DP state compression.
We will approach the problem using dynamic programming by maintaining a 3D DP table. The idea is to simulate two individuals traversing the grid simultaneously: one moving from (0,0) to (n-1,n-1) and the other returning from (n-1,n-1) back to (0,0). Both will walk through cells to collect cherries with the understanding that a cell’s cherry can be collected only once.
The DP table, dp[x1][y1][x2], represents the maximum cherries collected when person 1 is at (x1,y1) and person 2 is at (x2,y1+x1-x2) such that both paths have used same number of steps. Transitions are explored based on valid grid movements (right or down) and allowed combinations.
This method ensures we utilize optimal substructure and memoization to avoid computing the same state multiple times.
The implemented solution uses a 3D DP array where each state is represented by the positions of two players (x1, y1, x2) which directly determines (x2, y2) due to the step count equality of x1+y1 and x2+y2. Each entry fills based on maximum cherries collectable given their current step scenario, striving to improve from all possible move origins (right or down).
Time Complexity: O(n^3), due to iterating through each position combination for both players.
Space Complexity: O(n^3), the space needed to store results of all position combinations.
Given the constraints of the initial approach, further space optimization can be applied by minimizing the dimensions that are updated in the DP table at any given time. We'll reduce our 3D DP array into a 2D array considering only necessary state information, as they relate to specific grid traversals. This lowering of space dimensions capitalizes on the symmetrical nature of path reversals without sacrificing calculation correctness or granularity.
This solution keeps updating the 2D DP table along each step of a journey, maintaining only pertinent states per each t (sum of (x1 + y1)) layer. This slimmed-down model reduces memory burden significantly by recycling layers in place of ever-expanding a 3D matrix, aligning closely with each movement's iterative aspect.
Python
Time Complexity: O(n^3), iterating through elements optimized per journey line level.
Space Complexity: O(n^2), condensing memos to one comprehensive 2D table pairing.
According to the problem description, the player starts from (0, 0), reaches (n-1, n-1), and then returns to the starting point (0, 0). We can consider the player as starting from (0, 0) to (n-1, n-1) twice.
Therefore, we define f[k][i_1][i_2] as the maximum number of cherries that can be picked when both have walked k steps and reached (i_1, k-i_1) and (i_2, k-i_2) respectively. Initially, f[0][0][0] = grid[0][0]. The initial values of other f[k][i_1][i_2] are negative infinity. The answer is max(0, f[2n-2][n-1][n-1]).
According to the problem description, we can get the state transition equation:
$
f[k][i_1][i_2] = max(f[k-1][x_1][x_2] + t, f[k][i_1][i_2])
Where t represents the number of cherries at positions (i_1, k-i_1) and (i_2, k-i_2), and x_1, x_2 represent the previous step positions of (i_1, k-i_1) and (i_2, k-i_2) respectively.
The time complexity is O(n^3), and the space complexity is O(n^3). Where n$ is the side length of the grid.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with 3D DP Table | Time Complexity: O(n^3), due to iterating through each position combination for both players. Space Complexity: O(n^3), the space needed to store results of all position combinations. |
| Dynamic Programming with Space Optimization | Time Complexity: O(n^3), iterating through elements optimized per journey line level. Space Complexity: O(n^2), condensing memos to one comprehensive 2D table pairing. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with 3D DP Table | O(n^3) | O(n^3) | Best for understanding the core idea of modeling two synchronized paths |
| Dynamic Programming with Space Optimization | O(n^3) | O(n^2) | Preferred when memory usage matters or when optimizing DP state storage |
Cherry Pickup | Dynamic Programming Solution | Leetcode 741 • Pepcoding • 26,935 views views
Watch 9 more video solutions →Practice Cherry Pickup with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor