Show problems as
Classic problem #1463HardArrayDynamic ProgrammingMatrix

Cherry Pickup II

Real-world version: Two Arms Down the Parcel Wall
Tracked in this browser only
Read Cherry Pickup II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A warehouse wall is a grid wall, where wall[r][c] is the number of parcels sitting in that cell.

Two arms clear the wall. Arm one starts at the top-left cell (0, 0) and arm two starts at the top-right cell (0, cols - 1), where cols is the number of columns.

  • The arms move in lockstep. On each step both drop one row.
  • From cell (r, c) an arm may land on (r + 1, c - 1), (r + 1, c) or (r + 1, c + 1), and it must stay on the wall.
  • An arm takes every parcel in each cell it lands on, including the cell it starts from.
  • If both arms are on the same cell, the parcels there are taken once, not twice.
  • Both arms travel until they reach the bottom row.

Return the largest number of parcels the two arms can take between them.

Examples

Example 1

Input
wall = [[1, 2], [3, 4]]
Output
10

The starting cells give 1 and 2. On the only step the arms split the bottom row and take 3 and 4, for 10 parcels in all.

Example 2

Input
wall = [[0, 0, 0], [0, 100, 0]]
Output
100

The only parcels sit in the middle of the bottom row. Both arms can reach that cell, but a shared cell is emptied once, so the answer is 100.

Example 3

Input
wall = [[0, 0, 0, 0], [9, 9, 0, 0]]
Output
9

Arm one can only land on the first two columns of the bottom row and arm two on the last two. One arm reaches a loaded cell and the other cannot, so nine parcels come off the wall.

Constraints

  • 2 <= wall.length <= 70
  • 2 <= wall[i].length <= 70
  • 0 <= wall[i][j] <= 100

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def cherry_pickup(wall: list[list[int]]) -> int:
Java
public int cherryPickup(int[][] wall)

More on the same topics