773. Ninja and his Friends
Ninja has a grid of size R x C, where each cell contains some chocolates. He has two friends: Alice and Bob, and wants to collect as many chocolates as possible using their help.
- Alice starts at the top-left cell (0, 0)
- Bob starts at the top-right cell (0, C - 1)
- Both can only move to the next row, and from position (i, j), they can move to:
- (i + 1, j)
- (i + 1, j - 1)
- (i + 1, j + 1)
- Both must remain within the grid bounds.
- Each collects all chocolates in their current cell.
- If both land on the same cell, the chocolates are only counted once.
Return the maximum number of chocolates Ninja can collect using his two friends.
Example 1:
Input: grid = [[2, 3, 1, 2],[3, 4, 2, 2],[5, 6, 3, 5]]
Output: 21
Explanation:
- Alice: (0,0) → (1,1) → (2,1) → chocolates = 2 + 4 + 6 = 12
- Bob: (0,3) → (1,3) → (2,3) → chocolates = 2 + 2 + 5 = 9
- Total = 12 + 9 = 21
Example 2:
Input: grid = [[1, 2],[3, 4]]
Output: 10
Explanation:
- Alice: (0,0) → (1,0) → 1 + 3 = 4
- Bob: (0,1) → (1,1) → 2 + 4 = 6
- But both can’t pick at same time (if they land same cell), so:
- Best is (0,0)+(1,0)+(0,1)+(1,1) - overlap = 1+3+2+4 = 10
Now Your Turn!
Pick the correct output for the given inputInput: grid = [ [10, 1, 10], [1, 1, 1], [1, 1, 1]]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 2 <= R, C <= 50 — rows and columns of grid
- 0 <= grid[i][j] <= 100 — chocolates per cell