1463. Cherry Pickup II
Problem Description
In this problem, we're given a 2D grid representing a field of cherries, where each cell contains a certain number of cherries. We have two robots with the goal to collect as many cherries as possible. One robot starts at the top-left corner of the grid, and the other starts at the top-right corner. The objective is to move both robots to the bottom row, collecting cherries along the way, and to maximize the total number of cherries collected by both robots combined.
The robots can only move to the cell directly below them or diagonally to the left or right below them. This means from any cell (i, j), the next move can be to cells (i+1, j-1), (i+1, j), or (i+1, j+1). Additionally, if both robots end up on the same cell, only one of them can collect the cherries there, preventing double-counting.
The challenge is to find the path for both robots such that the total amount of cherries collected is maximized, considering they must follow the grid paths and cannot move outside the grid boundaries.
Intuition
To find the maximum number of cherries both robots can collect, we can use dynamic programming. This approach typically involves breaking down the problem into smaller subproblems that we solve and combine to find the final solution.
Here, we define a three-dimensional dynamic programming array dp[i][j1][j2]
where i
represents the current row, and j1
and j2
represent the columns of Robot 1 and Robot 2, respectively. The value stored in dp[i][j1][j2]
is the maximum number of cherries both robots can collect starting from row i
to the bottom of the grid, with Robot 1 at column j1
and Robot 2 at column j2
.
Since the robots can move to three different cells in the next row from their current position, we will consider all possible combinations of movements for both robots. We'll take the maximum of the valid moves, ensuring we avoid cells outside the grid boundaries.
The solution also considers that if both robots end up in the same cell, we only add the cherries from that cell once. After considering all possible movements for each row, the algorithm gradually builds up the solution, ending with the maximum count of cherries when the robots reach the bottom row.
The optimal value will be the maximum value found in dp[m-1][j1][j2]
, which represents the last row of the grid for any column positions j1
and j2
of the two robots.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution provided revolves around the principle of dynamic programming, where the problem's complexity is reduced by breaking it down into simpler subproblems and caching intermediate results for future reference.
Here, we follow these steps to implement the solution:
-
Initialization: We create two 2D arrays
f
andg
with dimensionsn x n
wheren
is the number of columns in the grid. They will hold the current and next state's maximum cherry counts respectively.f[0][n - 1]
is initialized with the sum of cherries from the starting positions of both robots (top-left and top-right). -
Iteration: We iterate through each row starting from the second row, as the first row is already covered by our initialization. During each iteration through rows
i
from1
tom - 1
(wherem
is the number of rows), we iterate through all columnsj1
andj2
for Robot 1 and Robot 2's positions, respectively. -
Cherry Collection (Nested Loop): For every possible position
(i, j1, j2)
of the robots, we calculate the cherry countx
that can be collected on rowi
considering both robots' positions, taking care not to double-count if they share the same cell. -
Transitions (Nested Loop within Nested Loop): Within the same loop, we check all possible previous positions
(i-1, y1, y2)
where the robots could have moved from. This involves looking at the rows right above and considering three possible positions for each robot. -
State Update: We update our next state
g[j1][j2]
with the maximum of the current value ing[j1][j2]
and the sum off[y1][y2]
andx
. This represents the maximum cherries from the previous step plus the current step's cherries. -
Transition to Next State: Once we've computed the values for all possible positions of
g
, we swapf
andg
so thatf
holds our next state's values when the next row iteration begins andg
is reset to be filled again. -
Final Result: Upon completing the row iterations, we have the maximum number of cherries that can be collected stored in the
f
array. To find the maximum, we iterate throughf
usingproduct(range(n), range(n))
to produce all combinations ofj1
andj2
locations and finding the maximum entry.
It's important to understand that dynamic programming is efficient here because we avoid recomputing maximum cherry counts for each subproblem, which would be the case in a naive recursive implementation. By storing these values in the 2D arrays, we only compute each subproblem once.
We use Python's tuple assignment to efficiently swap f
and g
arrays. The product function from itertools module is used to generate cartesian product of the column indices for the final result calculation. The algorithm's overall time complexity is O(mn^29), considering the size of the grid and the number of possible movements.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's consider a small example of a grid with 3 rows and 3 columns with the following number of cherries:
1grid = [ 2 [3, 1, 1], 3 [2, 5, 1], 4 [1, 5, 5] 5]
Robot 1 (R1) starts at the top left (cell with 3 cherries), and Robot 2 (R2) starts at the top right (cell with 1 cherry).
Initial State:
- Initialize
f
andg
with dimensions3 x 3
(since we have 3 columns), and setf[0][2]
with 4 (sum of cherries at R1's and R2's starting positions).
First Iteration (i=1, second row):
- Consider all combinations
(j1, j2)
, wherej1
andj2
are the column indices for R1 and R2, respectively. - R1 can move to positions
(1,0)
,(1,1)
, and(1,2)
, and R2 can move to positions(1,1)
,(1,2)
, and(1,3)
. Note:(1,3)
is invalid due to grid boundaries. - For each
(j1, j2)
, collect cherriesx
without double-counting if on the same cell and updateg[j1][j2]
with the maximum cherry count considering the previous positions(0, y1, y2)
.
Second Iteration (i=2, third row):
- Similar to the first iteration, we perform the nested loops and check all combinations of R1 and R2 moves from row 2 to row 3.
- Cherry collection and state update steps are similar but now for the third row.
Transitions and Final Result:
- After iteration through all rows, swap
f
andg
to prepare for the next row or to conclude with the final result. - The final result is the maximum number out of all entries in
f
to find the maximum cherries that both robots can collect.
Example Iteration Details:
- After the first step,
f
array hasf[0][2] = 4
since both robots start at opposite ends of the first row, 3+1 cherries collected. - For the next iteration (second row), let's assume
j1 = 1
andj2 = 1
(both robots are at the center). We collected 5 cherries since they both end up in the same cell.- When coming from
f
, check all possibley1, y2
to ensure we're adding the max previous value of cherries, sof[0][2]
+ cherries collected (5) for these positions and updateg[1][1]
accordingly. - After considering all combinations,
g
may look like this:1[0, 3, 0] 2[7, 0, 0] 3[0, 0, 0]
- When coming from
- After iterating through all rows, the robots will have collected a maximum number of cherries. In the final iteration, robots could end up at
f[2][0]
andf[2][2]
with the maximum sums obtained.f[2][0]
could have a sum of cherries collected from the first robot andf[2][2]
for the second robot.- Find the maximum entry in
f
to get the result.
Through this method, we have avoided double counting, and have systematically considered each possibility to ensure that the total number of cherries collected is maximized by the end when both robots have reached the bottom row. The result we'd obtain from the f
array would give us the max cherries collected.
Solution Implementation
1from itertools import product
2
3class Solution:
4 def cherry_pickup(self, grid: List[List[int]]) -> int:
5 # Get dimensions of the grid
6 rows, cols = len(grid), len(grid[0])
7
8 # Initialize the DP table f with -1, to store the cherries picked up for each (j1, j2) pair
9 f = [[-1] * cols for _ in range(cols)]
10
11 # Initialize temporary DP table to store the next row values
12 temp_dp = [[-1] * cols for _ in range(cols)]
13
14 # Base case initialization: starting at the first row
15 f[0][cols - 1] = grid[0][0] + grid[0][cols - 1]
16
17 # Start filling the DP table from the second row
18 for row in range(1, rows):
19 for j1 in range(cols):
20 for j2 in range(cols):
21 # Collect cherries for current positions (j1, j2), avoid double collecting if j1 == j2
22 cherries = grid[row][j1] + (0 if j1 == j2 else grid[row][j2])
23
24 # Transition from previous positions (y1, y2) to current (j1, j2)
25 for y1 in range(max(j1 - 1, 0), min(j1 + 2, cols)):
26 for y2 in range(max(j2 - 1, 0), min(j2 + 2, cols)):
27 if f[y1][y2] != -1: # Valid previous state
28 temp_dp[j1][j2] = max(temp_dp[j1][j2], f[y1][y2] + cherries)
29
30 # Swap the tables: make temp_dp the new DP table and reset temp_dp for the next iteration
31 f, temp_dp = temp_dp, [[-1] * cols for _ in range(cols)]
32
33 # Find the maximum cherries that can be collected for all (j1, j2) pairs in the last row
34 return max(f[j1][j2] for j1, j2 in product(range(cols), range(cols)))
35
1import java.util.Arrays;
2
3class Solution {
4 public int cherryPickup(int[][] grid) {
5 // m is the number of rows, n is the number of columns in the grid
6 int m = grid.length;
7 int n = grid[0].length;
8
9 // f[] stores the max cherries collected till the previous row
10 // g[] is used as a temporary array to store the results for the current row
11 int[][] dpPrevious = new int[n][n];
12 int[][] dpCurrent = new int[n][n];
13
14 // Initialize both arrays with -1 to indicate unvisited cells
15 for (int i = 0; i < n; ++i) {
16 Arrays.fill(dpPrevious[i], -1);
17 Arrays.fill(dpCurrent[i], -1);
18 }
19
20 // Since the two people start at opposite ends, we add their starting points
21 dpPrevious[0][n - 1] = grid[0][0] + grid[0][n - 1];
22
23 // Iterate through all rows starting from the second row
24 for (int i = 1; i < m; ++i) {
25 // Go through all possible positions of the two people (j1 and j2)
26 for (int j1 = 0; j1 < n; ++j1) {
27 for (int j2 = 0; j2 < n; ++j2) {
28 // x represents the cherries picked by both people;
29 // If they are at the same cell, only count the cherries once
30 int cherries = grid[i][j1] + (j1 == j2 ? 0 : grid[i][j2]);
31
32 // Consider all possible combinations for the previous positions of the two people
33 for (int y1 = j1 - 1; y1 <= j1 + 1; ++y1) {
34 for (int y2 = j2 - 1; y2 <= j2 + 1; ++y2) {
35 // Check if the previous positions are within the grid bounds and have been visited
36 if (y1 >= 0 && y1 < n && y2 >= 0 && y2 < n && dpPrevious[y1][y2] != -1) {
37 // Calculate the maximum cherries that can be collected for the current positions
38 dpCurrent[j1][j2] = Math.max(dpCurrent[j1][j2], dpPrevious[y1][y2] + cherries);
39 }
40 }
41 }
42 }
43 }
44
45 // Swap the references of dpPrevious and dpCurrent for the next iteration
46 int[][] temp = dpPrevious;
47 dpPrevious = dpCurrent;
48 dpCurrent = temp;
49
50 // Clear the secondary array after swapping to prepare for the next iteration
51 for (int i = 0; i < n; ++i) {
52 Arrays.fill(dpCurrent[i], -1);
53 }
54 }
55
56 // Answer variable to find the maximum of all dpPrevious values after completion
57 int maxCherries = 0;
58 for (int j1 = 0; j1 < n; ++j1) {
59 for (int j2 = 0; j2 < n; ++j2) {
60 maxCherries = Math.max(maxCherries, dpPrevious[j1][j2]);
61 }
62 }
63
64 // Return the maximum cherries that can be collected
65 return maxCherries;
66 }
67}
68
1class Solution {
2public:
3 int cherryPickup(vector<vector<int>>& grid) {
4 int rows = grid.size(), cols = grid[0].size();
5
6 // 'dpCurrent' holds the max cherries picked up to the i-th row for all column pairs (j1, j2).
7 vector<vector<int>> dpCurrent(cols, vector<int>(cols, -1));
8
9 // 'dpNext' to hold the temporary results for the next row computations.
10 vector<vector<int>> dpNext(cols, vector<int>(cols, -1));
11
12 // Initialize the first row situation where both persons start at the corners.
13 dpCurrent[0][cols - 1] = grid[0][0] + grid[0][cols - 1];
14
15 // Iterate over all rows of the grid starting from the second row (i=1).
16 for (int i = 1; i < rows; ++i) {
17 // Try all possible column positions for the first person (j1).
18 for (int j1 = 0; j1 < cols; ++j1) {
19 // Try all possible column positions for the second person (j2).
20 for (int j2 = 0; j2 < cols; ++j2) {
21 // Cherries picked up by the both persons - If on the same cell, don't double count.
22 int cherries = grid[i][j1] + (j1 == j2 ? 0 : grid[i][j2]);
23
24 // Consider all possible moves from previous row to current row for both persons
25 for (int prevJ1 = j1 - 1; prevJ1 <= j1 + 1; ++prevJ1) {
26 for (int prevJ2 = j2 - 1; prevJ2 <= j2 + 1; ++prevJ2) {
27 // If both previous positions are within bounds and a valid number of cherries was picked
28 if (prevJ1 >= 0 && prevJ1 < cols && prevJ2 >= 0 && prevJ2 < cols && dpCurrent[prevJ1][prevJ2] != -1) {
29 // Take the max between the current number of cherries and the newly computed value
30 dpNext[j1][j2] = max(dpNext[j1][j2], dpCurrent[prevJ1][prevJ2] + cherries);
31 }
32 }
33 }
34 }
35 }
36 // Update 'dpCurrent' with 'dpNext' and reset 'dpNext' for the next iteration.
37 swap(dpCurrent, dpNext);
38 fill(dpNext.begin(), dpNext.end(), vector<int>(cols, -1));
39 }
40
41 // Find the maximum number of cherries that can be picked by traversing the last row's 'dpCurrent'.
42 int maxCherries = 0;
43 for (int j1 = 0; j1 < cols; ++j1) {
44 for (int j2 = 0; j2 < cols; ++j2) {
45 maxCherries = max(maxCherries, dpCurrent[j1][j2]);
46 }
47 }
48 return maxCherries;
49 }
50};
51
1function cherryPickup(grid: number[][]): number {
2 const rowCount = grid.length; // Number of rows in the grid
3 const colCount = grid[0].length; // Number of columns in the grid
4
5 // dp1 stores the temporary results for cherry pickup
6 let dp1: number[][] = new Array(colCount).fill(0).map(() => new Array(colCount).fill(-1));
7
8 // dp2 is used for swapping with dp1 in each iteration
9 let dp2: number[][] = new Array(colCount).fill(0).map(() => new Array(colCount).fill(-1));
10
11 // Initial cherry count from both starting positions (0,0) and (0,colCount-1)
12 dp1[0][colCount - 1] = grid[0][0] + grid[0][colCount - 1];
13
14 // Iterate through each row
15 for (let row = 1; row < rowCount; ++row) {
16 // Go through all possible columns j1 and j2 for person 1 and 2 respectively
17 for (let col1 = 0; col1 < colCount; ++col1) {
18 for (let col2 = 0; col2 < colCount; ++col2) {
19 // Calculate the cherry count for the current positions col1 and col2
20 const cherryCount = grid[row][col1] + (col1 === col2 ? 0 : grid[row][col2]);
21 // Check all neighboring positions from the previous row
22 for (let prevCol1 = col1 - 1; prevCol1 <= col1 + 1; ++prevCol1) {
23 for (let prevCol2 = col2 - 1; prevCol2 <= col2 + 1; ++prevCol2) {
24 // If the new positions are within bounds and have a valid previous cherry count
25 if (prevCol1 >= 0 && prevCol1 < colCount &&
26 prevCol2 >= 0 && prevCol2 < colCount &&
27 dp1[prevCol1][prevCol2] !== -1) {
28 // Update the dp2 array with max cherry count for current positions
29 dp2[col1][col2] = Math.max(dp2[col1][col2], dp1[prevCol1][prevCol2] + cherryCount);
30 }
31 }
32 }
33 }
34 }
35 // Swap dp1 and dp2 for the next iteration
36 [dp1, dp2] = [dp2, dp1];
37 }
38
39 let maxCherries = 0; // Variable to store the max cherries collected
40 // Loop to find the maximum value in the last row of the dp1 array
41 for (let col1 = 0; col1 < colCount; ++col1) {
42 for (let col2 = 0; col2 < colCount; ++col2) {
43 maxCherries = Math.max(maxCherries, dp1[col1][col2]);
44 }
45 }
46 return maxCherries; // Return the maximum number of cherries collected
47}
48
Time and Space Complexity
Time Complexity
The time complexity of the algorithm is determined by the number of loops and the operations that occur inside them. There are three nested loops with respect to m
, n
, j1
, and j2
, resulting in a time complexity of O(m * n^2)
. Within the nested loops for j1
and j2
, there are two more loops for y1
and y2
. Each of these run through at most 3 iterations, which contributes a constant factor, not changing the asymptotic behavior. Therefore, the overall time complexity remains O(m * n^4)
.
Space Complexity
The space complexity of the algorithm comes from the f
and g
2D arrays that are used to store intermediate results. Both arrays have dimensions n x n
, so each array requires O(n^2)
space. Since there are two such arrays, you might initially think that this doubles the space requirement, but because they are swapped (f, g = g, f
), the total space complexity remains O(n^2)
as no additional space is required for the swapping operation.
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.