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] != -1The key insight for Cherry Pickup is to transform the forward and return trips into a single dynamic programming problem. Instead of thinking about one person going from the start to the end and back, imagine two travelers moving from the top-left to the bottom-right simultaneously. Both take the same number of steps at any time.
This allows us to define a DP state such as dp[r1][c1][r2], where the second column can be derived from the total steps. At each step, both travelers can move either right or down, creating four transition possibilities. If both land on the same cell, cherries should only be counted once. Cells with obstacles must be skipped, and invalid states should be ignored.
Using memoization or bottom-up DP, we compute the maximum cherries collectable across all valid transitions. This approach significantly reduces repeated work. The typical implementation runs in O(n^3) time with O(n^3) space, with possible optimizations to reduce memory usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| 3D Dynamic Programming (Memoization/Tabulation) | O(n^3) | O(n^3) |
| Space Optimized DP | O(n^3) | O(n^2) |
take U forward
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.
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.
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8 int cherryPickup(vector<vector<int>>& grid) {
9 int n = grid.size();
10 vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
11 dp[0][0][0] = grid[0][0];
12
13 for (int x1 = 0; x1 < n; ++x1) {
14 for (int y1 = 0; y1 < n; ++y1) {
15 for (int x2 = 0; x2 < n; ++x2) {
16 int y2 = x1 + y1 - x2;
17 if (y2 < 0 || y2 >= n || grid[x1][y1] == -1 || grid[x2][y2] == -1) {
18 continue;
19 }
20
21 int cherries = grid[x1][y1];
22 if (x1 != x2) {
23 cherries += grid[x2][y2];
24 }
25
26 if (x1 > 0) {
27 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1-1][y1][x2] + cherries);
28 }
29 if (y1 > 0) {
30 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1][y1-1][x2] + cherries);
31 }
32 if (x2 > 0) {
33 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1][y1][x2-1] + cherries);
34 }
35 if (y2 > 0) {
36 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1][y1][x2] + cherries);
37 }
38 }
39 }
40 }
41
42 return max(0, dp[n-1][n-1][n-1]);
43 }
44};The C++ solution is similar to the previous implementations, employing a 3D vector to calculate and save intermediate results for the amount of cherries collected. The vector enables efficient access and update across recursive computations, ensuring path-only valid states are considered, leveraging direct memory access benefits in C++.
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.
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.
1def cherryPickup(grid):
2 n = len(grid)
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Cherry Pickup is considered a challenging dynamic programming problem and has appeared in high-level technical interviews. It tests understanding of multidimensional DP, state transitions, and grid-based optimization problems.
The optimal approach uses dynamic programming by modeling two people moving through the grid simultaneously. A 3D DP state tracks the positions of both travelers and calculates the maximum cherries collected while avoiding blocked cells.
A 3D dynamic programming table or memoization cache is commonly used. It stores intermediate results for combinations of positions so the algorithm can efficiently reuse previously computed states.
The forward and backward paths share overlapping states, which makes the problem difficult if treated separately. Modeling two travelers moving from the start to the end at the same time simplifies the state transitions and avoids recomputation.
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.