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.
You have two robots that can collect cherries for you:
(0, 0), and(0, cols - 1).Return the maximum number of cherries collection using both robots by following the rules below:
(i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).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] <= 100This approach involves using a dynamic programming table to store intermediate results. The state dp[r][c1][c2] represents the maximum cherries we can collect when robot 1 is at position (r, c1) and robot 2 is at (r, c2). The transition involves moving both robots to the next row and trying all possible column moves for each robot.
This function implements a dynamic programming solution. We use a 3D table dp where dp[r][c1][c2] represents the maximum cherries obtainable starting from row r with robot 1 at column c1 and robot 2 at column c2. We transition backwards from the last row to the first row, checking all possible moves for the robots.
C++
Time Complexity: O(rows * cols^2)
Space Complexity: O(rows * cols^2)
This approach uses a recursive function with memoization to calculate the maximum cherries possible. The function recursively tries all valid ways the robots can move to the next row from their current columns, caching results to prevent redundant calculations.
The Java solution uses recursion with memoization, where dfs is the recursive function that calculates the maximum cherries possible from any given position, storing results in memo to optimize repeat calculations. Each call considers new positions for the robots in the next row.
JavaScript
Time Complexity: O(rows * cols^2)
Space Complexity: O(rows * cols^2) for memoization
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(rows * cols^2) |
| Recursive Approach with Memoization | Time Complexity: O(rows * cols^2) |
DP 13. Cherry Pickup II | 3D DP Made Easy | DP On Grids • take U forward • 280,890 views views
Watch 9 more video solutions →Practice Cherry Pickup II with our built-in code editor and test cases.
Practice on FleetCode