Cherry Pickup II

Hard

Topics
ArrayDynamic ProgrammingMatrix

Given a grid where each cell holds a number of cherries, two robots start at the top-left (0,0) and top-right (0, cols-1). Each robot moves down one row at a time to a diagonally-left, straight-down, or diagonally-right cell. When a robot passes a cell it collects its cherries; if both robots are on the same cell only one collection counts. Return the maximum cherries both robots can collect together after reaching the bottom row.

Example 1

Input:  grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24

Example 2

Input:  grid = [[5]]
Output: 5

Constraints

  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100
Run ⌘' · Submit ⌘⏎