Ninja and his Friends
MediumTwo positions, one shared row
Problem
Two players collect chocolates from a grid moving down; maximize combined chocolates without both taking the same cell.
Two paths move down together; DP over both column positions, adding the shared cell only once.
The idea
Both players move down one row at a time, so the state is (row, column of player one, column of player two) and each step tries all nine move combinations. When they land on the same cell, count the chocolates once.
The trick
- State is one row plus two columns — the players stay in step.
- Nine transitions per state, from three moves each.
- Same cell means count once, not twice.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — grid Values: 0.
1dp[i][j1][j2] over 9 move combinations of the two playersInput
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
- Output:
- 24
- Explanation:
- Two collectors gather a max of 24 cherries.
Example 2
- Input:
- grid = [[1,1],[1,1]]
- Output:
- 4
- Explanation:
- Both start in corners → 4.
Example 3
- Input:
- grid = [[7]]
- Output:
- 7
- Explanation:
- One cell shared → 7.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.