Two Pickers Down the Field
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
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
With one column both stand on the same cell, and its berries count once.
Constraints
1 <= len(grid) <= 201 <= len(grid[0]) <= 12, and every row has that length0 <= grid[r][c] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Two Towers of One HeightHard
- Factorials Up to nBeginner
- Fibonacci NumberBeginner
- Frog Across the StonesBeginner
- Hop One or ThreeBeginner
- N-th Tribonacci NumberBeginner
- Paving With Colored SlabsBeginner
- Pell NumbersBeginner