Cherry Pickup
Hard · Dynamic Programming · Array · Dynamic Programming · Matrix
Problem
You are given an n x n field grid. Each cell is 1 (a cherry you can pick), 0 (empty) or -1 (a thorn bush you cannot enter).
Starting at (0, 0), walk to (n - 1, n - 1) moving only right or down through non-thorn cells, then walk back to (0, 0) moving only left or up through non-thorn cells. Whenever you pass a cell with a cherry you collect it and the cell becomes 0.
Return the maximum number of cherries you can collect on the round trip. If there is no valid path from (0, 0) to (n - 1, n - 1), return 0.
Examples
Input: grid = [[1,1,0],[0,-1,1],[1,1,1]] Output: 6
Go out along the top row and down the right column, then come back along the bottom row and up the left column, collecting all 6 cherries.
Input: grid = [[1,-1],[-1,1]] Output: 0
Both routes out of the start are blocked, so no trip is possible.
Input: grid = [[1,1,1,1,0,0,0],[0,0,0,1,0,0,0],[0,0,0,1,0,0,1],[1,0,0,1,0,0,0],[0,0,0,1,0,0,0],[0,0,0,1,0,0,0],[0,0,0,1,1,1,1]] Output: 15
The best single path takes the 13 cherries on the long route; the two left, at (3, 0) and (2, 6), cannot both be reached by one more path, so going greedy gets 14. Planned together, two paths take all 15.
Constraints
- n == len(grid) == len(grid[i])
- 1 <= n <= 50
- Each grid[i][j] is -1, 0 or 1
- grid[0][0] != -1 and grid[n - 1][n - 1] != -1
Approaches
- Every first path, then the best way back — time O(C(2n-2, n-1) · n²), space O(n²)
Follow-up
What if both walkers start on the top row, one in each corner, and each step moves down one row and to any of the three columns below? Then the shared clock is the row, the state is the pair of columns, and the same "count a shared cell once" rule applies, in O(rows · cols²) states with nine moves each.
Related problems
Start free on Cariara · Coding problems · System design studio
