hardDynamic Programming 2DPure DSA~40 min
Two Collectors Descending a Reward Grid
Two collector bots start at the top corners of a reward grid and descend to the bottom row, each moving down-left, down, or down-right per step. They share rewards on overlap. Maximize the total collected.
Problem
Given an m x n grid of non-negative rewards, two robots start at (0,0) and (0,n-1). Each robot moves to the next row at column c-1, c, or c+1. When both robots occupy the same cell, the reward is counted once. After both reach the last row, return the maximum total reward collected.
Input
An m x n grid of non-negative integers.
Output
An integer: the maximum combined reward.
Constraints
- 2 <= m, n <= 70
- 0 <= grid[i][j] <= 100
Examples
Example 1
Input
grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output
24
The two robots' optimal descents collect 24 in total.
Example 2
Input
grid = [[1,1],[1,1]]
Output
4
Robots in separate columns collect all four cells.