FunctionRacerProblemsRace

Two Pickers Down the Field

HardDynamic programmingPython, JavaScript, TypeScript, Java, C++

grid[r][c] is the number of berries in a cell of a field. Two pickers start in the top row, one in the leftmost cell and one in the rightmost cell. With every step both move one row down, each to the cell straight below or to the one left or right of it, and they never leave the field.

A picker takes all the berries of every cell they stand on, the start included. A cell that both stand on gives its berries once. Return the most berries the two can pick together by the time they reach the bottom row.

Example 1

grid [[1,0,2],[0,9,0],[4,0,3]]
returns 19

They start with 1 + 2. One steps to the 9 and then to the 4, the other goes straight down to the 3: 3 + 9 + 4 + 3 = 19.

Example 2

grid [[5],[2]]
returns 7

With one column both stand on the same cell, and its berries count once.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems