You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.
Here’s the [Problem Link] to begin with.
You have two robots that can collect cherries for you:
- Robot #1 is located at the top-left corner
(0, 0), and - Robot #2 is located at the top-right corner
(0, cols - 1).
Return the maximum number of cherries collection using both robots by following the rules below:
- From a cell
(i, j), robots can move to cell(i + 1, j - 1),(i + 1, j), or(i + 1, j + 1). - When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
- When both robots stay in the same cell, only one takes the cherries.
- Both robots cannot move outside of the grid at any moment.
- Both robots should reach the bottom row in
grid.
Example 1:
Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.
Example 2:
Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.
Constraints:
rows == grid.lengthcols == grid[i].length2 <= rows, cols <= 700 <= grid[i][j] <= 100
Solution 1: Recursion (Brute Force)
Intuition
Model the process as both robots moving row by row. At each row i, robot 1 can move to j1 + {-1, 0, +1}, and robot 2 to j2 + {-1, 0, +1}. For each pair of moves (3 x 3 = 9 combinations), compute cherries collected on current row and add the maximum of the recursive results for the next row. If both robots are on the same cell, count grid[i][j1] once; otherwise, sum grid[i][j1] + grid[i][j2]. Out-of-bound moves yield negative infinity to invalidate those paths.
Detailed Approach
- Base conditions:
- If any column is out of bounds, return -inf to invalidate.
- If at the last row, return grid[i][j1] if j1 == j2 else grid[i][j1] + grid[i][j2].
- Transition:
- Try all 9 moves for (new_j1, new_j2) in {-1, 0, +1} x {-1, 0, +1}, accumulate current cherries, and take the maximum.
Code
class Solution:
def solve(self, i, j1, j2, grid):
# If any robot goes out of bounds, path is invalid
if j1 < 0 or j1 >= len(grid[0]) or j2 < 0 or j2 >= len(grid):
return float("-inf")
# If last row: collect once if same cell else sum both
if i == len(grid) - 1:
if j1 == j2:
return grid[i][j1]
return grid[i][j1] + grid[i][j2]
maxi = 0
# Explore all 9 move combinations for both robots
for new_j1 in range(-1, 2):
for new_j2 in range(-1, 2):
if j1 == j2:
ans = grid[i][j1] + self.solve(
i + 1, j1 + new_j1, j2 + new_j2, grid
)
else:
ans = (
grid[i][j1]
+ grid[i][j2]
+ self.solve(i + 1, j1 + new_j1, j2 + new_j2, grid)
)
maxi = max(maxi, ans)
return maxi
def cherryPickup(self, grid: List[List[int]]) -> int:
# Start with robot1 at col 0 and robot2 at col m-1
return self.solve(0, 0, len(grid) - 1, grid)Code Explanation
- The recursive function explores all combinations of moves for both robots.
- It ensures invalid moves are discarded and correctly handles the “same cell” case.
- The main function starts from the top row with robots at columns 0 and m-1.
Time and Space Complexity
- Precise: Time O(9^(n)) in worst case due to branching over 9 moves per row; Space O(n) for recursion depth.
- Simplified: Exponential time; linear recursion space.
Conclusion
This gives the right answer but is impractical for larger n and m due to heavy recomputation.
Solution 2: Memoization (Top-Down DP)
Intuition
The recursive state repeats for the same (i, j1, j2). Cache the maximum cherries for each state in a 3D DP table dp[i][j1][j2]. This reduces the complexity dramatically since each state is computed once.
Detailed Approach
- Use dp with dimensions n x m x m initialized to -1.
- Before computing a state, return dp[i][j1][j2] if it’s already known.
- Otherwise, compute as in recursion, store the best in dp[i][j1][j2], and return it.
Code
class Solution:
def solve(self, i, j1, j2, grid, dp):
# Boundary checks
if j1 < 0 or j1 >= len(grid) or j2 < 0 or j2 >= len(grid):
return float("-inf")
# Base case at last row
if i == len(grid) - 1:
if j1 == j2:
return grid[i][j1]
return grid[i][j1] + grid[i][j2]
# Return cached result if computed
if dp[i][j1][j2] != -1:
return dp[i][j1][j2]
maxi = 0
# Try all move pairs
for new_j1 in range(-1, 2):
for new_j2 in range(-1, 2):
if j1 == j2:
ans = grid[i][j1] + self.solve(
i + 1, j1 + new_j1, j2 + new_j2, grid, dp
)
else:
ans = (
grid[i][j1]
+ grid[i][j2]
+ self.solve(i + 1, j1 + new_j1, j2 + new_j2, grid, dp)
)
maxi = max(maxi, ans)
dp[i][j1][j2] = maxi
return dp[i][j1][j2]
def cherryPickup(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid)
# DP dimensions: N x M x M
dp = [[[-1 for _ in range(m)] for _ in range(m)] for _ in range(n)]
return self.solve(0, 0, len(grid) - 1, grid, dp)Code Explanation
- The memo table stores the best result for every (row, col1, col2).
- This eliminates overlapping subproblems and makes the solution efficient.
Time and Space Complexity
- Precise: Time O(n × m × m × 9) ≈ O(n × m²); Space O(n × m²) for dp plus O(n) recursion stack.
- Simplified: Time O(n m²), Space O(n m²).
Conclusion
Memoization turns the exponential recursion into a polynomial-time solution suitable for constraints up to 70.
Solution 3: Tabulation (Bottom-Up DP)
Intuition
Build dp from the last row upward. For each row i and column pair (j1, j2), compute the best by considering all next moves (9 options) using the values from row i+1. Initialize the base row directly from the grid.
Detailed Approach
- Define dp[i][j1][j2] = maximum cherries from row i when robots are at (j1, j2).
- Base: For i = n-1, dp[n-1][j1][j2] = grid[n-1][j1] if j1 == j2 else grid[n-1][j1] + grid[n-1][j2].
- Transition: For each i from n-2 down to 0, and each j1, j2, compute max over valid next positions using dp[i+1][…].
Code
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid)
dp = [[[-1 for _ in range(m)] for _ in range(m)] for _ in range(n)]
# Base cases for last row
for j1 in range(m):
for j2 in range(m):
if j1 == j2:
dp[n - 1][j1][j2] = grid[n - 1][j1]
else:
dp[n - 1][j1][j2] = grid[n - 1][j1] + grid[n - 1][j2]
# Fill from bottom to top
for i in range(n - 2, -1, -1):
for j1 in range(m):
for j2 in range(m):
maxi = 0
for new_j1 in range(-1, 2):
for new_j2 in range(-1, 2):
if (
j1 + new_j1 < 0
or j2 + new_j2 < 0
or j1 + new_j1 >= m
or j2 + new_j2 >= m
):
ans = float("-inf")
elif j1 == j2:
ans = grid[i][j1] + dp[i + 1][j1 + new_j1][j2 + new_j2]
else:
ans = (
grid[i][j1]
+ grid[i][j2]
+ dp[i + 1][j1 + new_j1][j2 + new_j2]
)
maxi = max(maxi, ans)
dp[i][j1][j2] = maxi
return dp[0][0][m - 1]Code Explanation
- Initializes the last row where only immediate cherries matter.
- For each upper row, aggregates the best future gains from the next row by exploring 9 possibilities.
- The final answer is dp[m-1], matching the start positions.
Time and Space Complexity
- Precise: Time O(n × m × m × 9) ≈ O(n × m²); Space O(n × m²).
- Simplified: Time O(n m²), Space O(n m²).
Conclusion
This bottom-up approach avoids recursion and is easy to iterate and debug.
Solution 4: Tabulation (Space Optimization)
Intuition
At row i, you only need results from row i+1. Replace the 3D dp with two 2D layers: prev for row i+1 and curr for row i. Roll these layers as you move up to save memory from O(n m²) to O(m²).
Detailed Approach
- Initialize prev as the base row (n-1).
- For each upper row, compute curr[j1][j2] using prev for next positions.
- After finishing a row, set prev = curr and continue upward.
- Final answer is in prev[m-1] after processing row 0.
Code
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid)
# Base: last row layer
prev = [[-1 for _ in range(m)] for _ in range(m)]
for j1 in range(m):
for j2 in range(m):
if j1 == j2:
prev[j1][j2] = grid[n - 1][j1]
else:
prev[j1][j2] = grid[n - 1][j1] + grid[n - 1][j2]
# Build upwards using rolling 2D arrays
for i in range(n - 2, -1, -1):
curr = [[-1 for _ in range(m)] for _ in range(m)]
for j1 in range(m):
for j2 in range(m):
maxi = 0
for new_j1 in range(-1, 2):
for new_j2 in range(-1, 2):
if (
j1 + new_j1 < 0
or j2 + new_j2 < 0
or j1 + new_j1 >= m
or j2 + new_j2 >= m
):
ans = float("-inf")
elif j1 == j2:
ans = grid[i][j1] + prev[j1 + new_j1][j2 + new_j2]
else:
ans = (
grid[i][j1]
+ grid[i][j2]
+ prev[j1 + new_j1][j2 + new_j2]
)
maxi = max(maxi, ans)
curr[j1][j2] = maxi
prev = curr
return prev[m - 1]Code Explanation
- Stores only two layers at any time: the current row’s DP and the next row’s DP.
- Uses the same transition logic as tabulation but with reduced memory.
Time and Space Complexity
- Precise: Time O(n × m × m × 9) ≈ O(n × m²); Space O(m²) for two 2D layers.
- Simplified: Time O(n m²), Space O(m²).
Conclusion
This is the interview-ready optimal DP: minimal space with the same time complexity and clean rolling-state logic.
Final Notes and Tips
- Always handle the “same cell” case by counting cherries once.
- Use -inf for invalid moves to naturally exclude them from max computations.
- The 3D state (i, j1, j2) encodes both robots’ positions; transitions are the 9 combined moves per step.
- For constraints up to 70×70, O(n m²) with memoization or tabulation runs comfortably.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
