Skip to main content

741. Cherry Pickup

hard

Walk from top-left to bottom-right and back, collecting the maximum cherries. Reframed as two simultaneous paths whose state is a 1D column-pair after diagonalization.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers. 0 means the cell is empty, so you can pass through, 1 means the cell contains a cherry that you can pick up and pass through, or -1 means the cell contains a thorn that blocks your way. Return the maximum number of cherries you can collect by following the rules below: Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1). After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells. When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0. If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.

Constraints

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 50
  • grid[i][j] is -1, 0, or 1.
  • grid[0][0] != -1
  • grid[n - 1][n - 1] != -1

Examples

Example 1

Input
grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output
5

Explanation: The player started at (0, 0) and went down, down, right, right reaching (2, 2). 4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]]. Then, the player went left, up, up, left returning home, picking up one more cherry. The total number of cherries picked up is 5, and this is the maximum possible.

Example 2

Input
grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Going forward then backward equals two simultaneous forward walkers from (0,0) to (n-1,n-1).

Hint 2

Both walkers move at the same speed: after k steps each is at some (r, k-r). State collapses to (step, c1, c2).

Hint 3

For fixed step k, dp is indexed by the pair of columns — effectively a 1D-over-column-pairs DP rolled forward.

Solution approach

Reveal approach

Reframe: instead of one walker going forward then backward, run two walkers simultaneously forward from (0, 0) to (n-1, n-1). After exactly k steps each walker is on the anti-diagonal r + c = k, so the rows are r1 = k - c1 and r2 = k - c2. The state collapses to (k, c1, c2). Maintain a 2D dp keyed on (c1, c2) for the current step and roll forward step by step. Transition: from step k to k+1 each walker independently moves right or down — four combinations. Block any state where either cell is -1. If the walkers land on the same cell, count its cherry only once. Return max(0, dp at the final step at (n-1, n-1)). O(n^3) time, O(n^2) per step.

Complexity

Time
O(n^3)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

More DP 1D practice problems

See all DP 1D problems →