Cherry Pickup II
Hard · Dynamic Programming · Array · Dynamic Programming · Matrix
Problem
A rows × cols grid holds cherries: grid[i][j] is the number in cell (i, j). Two robots start on the top row, robot 1 at (0, 0) and robot 2 at (0, cols - 1).
Both robots move down one row at the same time. From (i, j) a robot moves to (i + 1, j - 1), (i + 1, j) or (i + 1, j + 1), and it may never leave the grid. A robot picks every cherry in each cell it visits, its starting cell included. When both robots stand in the same cell, its cherries are counted once.
The robots stop on the bottom row. Return the largest number of cherries they can pick together.
Examples
Input: grid = [[1,0,0,2],[0,4,3,0],[2,0,0,1]] Output: 13
Robot 1 picks 1, 4, 2 and robot 2 picks 2, 3, 1: 7 + 6 = 13.
Input: grid = [[5,5],[5,5]] Output: 20
Each robot stays in its own column, so all four cells are picked: 20.
Input: grid = [[1,0,1],[0,9,0],[1,1,1]] Output: 13
Only one robot can take the 9 in the middle (it counts once if both go there): 1 + 9 + 1 for one robot, 1 + 0 + 1 for the other, 13 in all.
Constraints
- rows == len(grid), cols == len(grid[i])
- 2 <= rows, cols <= 70
- 0 <= grid[i][j] <= 100
Approaches
- Try every pair of paths — time O(9^rows), space O(rows) for the recursion
Follow-up
Can the table be cut in half? A robot that starts on the left never needs to cross the other one: swapping their paths at a crossing gives the same cherries. So only pairs with a <= b matter, which halves the work. With three robots the state becomes three columns, O(rows · cols³ · 27), and the same lockstep idea still applies.
Related problems
Start free on Cariara · Coding problems · System design studio
