1083HardArrayDynamic ProgrammingMatrix

Two Arms Down the Parcel Wall

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def cherry_pickup(wall: list[list[int]]) -> int:

Java

public int cherryPickup(int[][] wall)

The intended approach

Time O(rows * cols^2) states with a fixed nine moves each.Space O(cols^2) for two tables of column pairs.

Because the arms drop exactly one row per step, after `r` steps both sit in row `r`. All that is left to say about the pair is which two columns they occupy, so a row plus a pair of columns is the whole state, and the future depends on nothing else. That makes a row-by-row sweep enough. Hold a table over pairs of columns giving the most parcels collectable to reach that pair in the current row. Seed row zero with the single reachable pair, the two outer columns, worth their two cells. To move to the next row, take every reachable pair and every one of the nine combinations of sideways steps, keep the ones that stay on the wall, and add the parcels in the two cells landed on, counting the cell once when the two arms land together. Keep the best value found for each new pair. The answer is the largest entry in the table after the bottom row is processed. Pairs never reached stay marked as impossible so they cannot leak into a result.

Pythonentry point: cherry_pickup

def cherry_pickup(wall):
    rows = len(wall)
    cols = len(wall[0])
    best = [[-1] * cols for _ in range(cols)]
    best[0][cols - 1] = wall[0][0] + wall[0][cols - 1]
    for r in range(1, rows):
        nxt = [[-1] * cols for _ in range(cols)]
        for a in range(cols):
            for b in range(cols):
                base = best[a][b]
                if base < 0:
                    continue
                for da in (-1, 0, 1):
                    na = a + da
                    if na < 0 or na >= cols:
                        continue
                    for db in (-1, 0, 1):
                        nb = b + db
                        if nb < 0 or nb >= cols:
                            continue
                        gain = wall[r][na]
                        if nb != na:
                            gain += wall[r][nb]
                        if base + gain > nxt[na][nb]:
                            nxt[na][nb] = base + gain
        best = nxt
    answer = 0
    for a in range(cols):
        for b in range(cols):
            if best[a][b] > answer:
                answer = best[a][b]
    return answer

The obvious version

Walk every possible pair of routes with plain recursion and no memory. At each row add the parcels of the two cells the arms stand on, once if they stand together, then branch on all nine pairs of sideways steps that stay on the wall and keep the best. Costs nine to the power of the row count, so it only survives a handful of rows.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_cherry_pickup(wall):
    rows = len(wall)
    cols = len(wall[0])

    def walk(r, a, b):
        gain = wall[r][a]
        if b != a:
            gain += wall[r][b]
        if r == rows - 1:
            return gain
        best = -1
        for da in (-1, 0, 1):
            na = a + da
            if na < 0 or na >= cols:
                continue
            for db in (-1, 0, 1):
                nb = b + db
                if nb < 0 or nb >= cols:
                    continue
                sub = walk(r + 1, na, nb)
                if sub > best:
                    best = sub
        return gain + best

    return walk(0, 0, cols - 1)

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in