Skip to main content

741. Cherry Pickup

hard

Walk from the top-left of an n x n grid to the bottom-right and back, collecting cherries; thorns block cells. The trick: instead of two passes, simulate two walkers moving forward simultaneously and let them share a 4D DP state.

By Alex Chen, 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 to reach (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 to return 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

A greedy round-trip fails: the best first trip can starve the second. Solve both legs together.

Hint 2

Two walkers both start at (0, 0) and both move right or down to (n-1, n-1). They take the same number of steps, so r1 + c1 == r2 + c2 == step.

Hint 3

State (step, r1, r2) determines c1 = step - r1 and c2 = step - r2 — so the DP is 3D, not 4D.

Hint 4

If both walkers stand on the same cell, count its cherry only once. Thorns return -infinity.

Solution approach

Reveal approach

Reformulate as two walkers moving simultaneously from (0, 0) to (n-1, n-1). Let dp[r1][r2][step] be the maximum cherries collected by two walkers at row r1 and r2 with c1 = step - r1 and c2 = step - r2. Transition: each walker can come from above or from the left, giving four combinations of predecessor states. Add the cherry at (r1, c1) and at (r2, c2), but only once when (r1, c1) == (r2, c2). If either cell is a thorn or out of bounds, the state is -infinity. Top-down memoization on (r1, c1, r2) is the typical implementation since c2 is determined. Final answer is max(0, dp[n-1][n-1][2n-2]).

Complexity

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

Related patterns

  • dynamic-programming
  • grid-dp
  • multi-agent-dp

Related problems

Asked at

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

  • Google

Practice these live with InterviewChamp.AI

Drill Cherry Pickup and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →