Ninja and his friends
Description
Ninja has a grid of size R × C filled with chocolates. Each cell grid[i][j] holds a certain number of chocolates. Ninja enlists two friends — Alice and Bob — to help collect as many chocolates as possible.
Alice begins at the top-left corner (0, 0) and Bob begins at the top-right corner (0, C - 1). Both move simultaneously, advancing exactly one row per step from top to bottom. From any cell (i, j), a person can move to one of three cells in the next row:
(i + 1, j - 1)— diagonal left(i + 1, j)— straight down(i + 1, j + 1)— diagonal right
Neither person may step outside the grid boundaries.
When someone passes through a cell, they collect all its chocolates, leaving the cell empty. If both Alice and Bob occupy the same cell in the same row, only one of them picks up the chocolates.
Return the maximum total chocolates that Alice and Bob can collect together by the time they both reach the last row.
Examples
Example 1
Input: R = 3, C = 4
grid = [[2, 3, 1, 2], [3, 4, 2, 2], [5, 6, 3, 5]]
Output: 21
Explanation: Alice follows the path (0,0) → (1,1) → (2,1) and collects 2 + 4 + 6 = 12 chocolates. Bob follows the path (0,3) → (1,3) → (2,3) and collects 2 + 2 + 5 = 9 chocolates. Their paths never overlap, so the total is 12 + 9 = 21. No other combination of paths yields a higher total.
Example 2
Input: R = 2, C = 2
grid = [[1, 1], [1, 2]]
Output: 5
Explanation: Alice starts at (0,0) and Bob starts at (0,1). In row 0, Alice collects 1 and Bob collects 1 (total so far: 2). Moving to row 1: Alice goes to (1,0) collecting 1, and Bob goes to (1,1) collecting 2. Total = 1 + 1 + 1 + 2 = 5. If both moved to the same cell in row 1, one of them would miss chocolates, giving a worse result.
Constraints
- 2 ≤ R, C ≤ 50
- 0 ≤ grid[i][j] ≤ 100
Editorial
Brute Force - Recursion
Intuition
The most natural way to tackle this problem is to simulate every possible pair of paths for Alice and Bob. At each row, Alice has up to 3 choices (move diagonal-left, straight down, or diagonal-right) and Bob independently has up to 3 choices. Since their decisions are independent, there are up to 3 × 3 = 9 combinations of moves per row.
We define a recursive function solve(row, j1, j2) that returns the maximum chocolates collectible from row row to the last row, given Alice is at column j1 and Bob is at column j2. The answer is solve(0, 0, C - 1).
Handling the overlap case is straightforward: if j1 == j2, both people are on the same cell, so we count the chocolates only once. Otherwise, we add grid[row][j1] + grid[row][j2].
At each step, we try all 9 combinations of moves for Alice and Bob, recurse into the next row, and return the maximum result.
Step-by-Step Explanation
Let's trace through with grid = [[2, 3, 1, 2], [3, 4, 2, 2], [5, 6, 3, 5]] (R=3, C=4):
Step 1: Call solve(0, 0, 3). Alice is at column 0, Bob at column 3 in row 0. Different columns, so collect grid[0][0] + grid[0][3] = 2 + 2 = 4.
Step 2: From row 0, Alice at col 0 can reach {0, 1} in row 1. Bob at col 3 can reach {2, 3} in row 1. This gives 4 valid children: solve(1, 0, 2), solve(1, 0, 3), solve(1, 1, 2), solve(1, 1, 3). We must try ALL of them.
Step 3: Explore solve(1, 0, 2). Alice col 0, Bob col 2. Collect grid[1][0] + grid[1][2] = 3 + 2 = 5. This call further branches into 6 children for row 2.
Step 4: One child is solve(2, 0, 1). Row 2 is the last row (base case). grid[2][0] + grid[2][1] = 5 + 6 = 11. Return 11.
Step 5: Another child is solve(2, 1, 3). Base case: grid[2][1] + grid[2][3] = 6 + 5 = 11. Return 11.
Step 6: After evaluating all 6 children of solve(1, 0, 2), the best child returns 11. So solve(1, 0, 2) = 5 + 11 = 16.
Step 7: Now explore solve(1, 1, 3). Alice col 1, Bob col 3. Collect grid[1][1] + grid[1][3] = 4 + 2 = 6. It also has children including solve(2, 1, 3).
Step 8: solve(2, 1, 3) is called again — the same state as Step 5! Without memoization, brute force recomputes the entire subtree. Result: 11 (same as before, but the work is repeated).
Step 9: solve(1, 1, 3) = 6 + 11 = 17. This is better than solve(1, 0, 2) = 16.
Step 10: Back at the root, solve(0, 0, 3) compares all children. The best is 17 from solve(1, 1, 3). Final answer: 4 + 17 = 21.
Brute Force Recursion — Exponential Branching — Watch how the recursive calls branch exponentially, and notice that solve(2,1,3) is computed twice — once from each parent — wasting work.
Algorithm
- Define
solve(row, j1, j2)— returns max chocolates from rowrowto the last row with Alice at colj1and Bob at colj2 - Base case: If
j1orj2is out of bounds, return negative infinity. Ifrow == R - 1(last row), returngrid[row][j1](plusgrid[row][j2]ifj1 ≠ j2) - Collect: If
j1 == j2, collectgrid[row][j1]. Otherwise collectgrid[row][j1] + grid[row][j2] - Recurse: Try all 9 combinations of
(dj1, dj2)where each is in {-1, 0, +1}. Recurse intosolve(row + 1, j1 + dj1, j2 + dj2). Keep the maximum - Return collected chocolates + best recursive result
- Answer:
solve(0, 0, C - 1)
Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(int row, int j1, int j2, int R, int C,
vector<vector<int>>& grid) {
if (j1 < 0 || j1 >= C || j2 < 0 || j2 >= C)
return -1e8;
if (row == R - 1) {
if (j1 == j2) return grid[row][j1];
return grid[row][j1] + grid[row][j2];
}
int maxVal = -1e8;
for (int dj1 = -1; dj1 <= 1; dj1++) {
for (int dj2 = -1; dj2 <= 1; dj2++) {
int val = (j1 == j2)
? grid[row][j1]
: grid[row][j1] + grid[row][j2];
val += solve(row + 1, j1 + dj1, j2 + dj2,
R, C, grid);
maxVal = max(maxVal, val);
}
}
return maxVal;
}
int maximumChocolates(int R, int C,
vector<vector<int>>& grid) {
return solve(0, 0, C - 1, R, C, grid);
}
};class Solution:
def maximumChocolates(self, R: int, C: int,
grid: list[list[int]]) -> int:
def solve(row, j1, j2):
if j1 < 0 or j1 >= C or j2 < 0 or j2 >= C:
return float('-inf')
if row == R - 1:
if j1 == j2:
return grid[row][j1]
return grid[row][j1] + grid[row][j2]
max_val = float('-inf')
for dj1 in range(-1, 2):
for dj2 in range(-1, 2):
val = grid[row][j1] if j1 == j2 \
else grid[row][j1] + grid[row][j2]
val += solve(row + 1, j1 + dj1, j2 + dj2)
max_val = max(max_val, val)
return max_val
return solve(0, 0, C - 1)class Solution {
int solve(int row, int j1, int j2, int R, int C,
int[][] grid) {
if (j1 < 0 || j1 >= C || j2 < 0 || j2 >= C)
return (int) -1e8;
if (row == R - 1) {
if (j1 == j2) return grid[row][j1];
return grid[row][j1] + grid[row][j2];
}
int maxVal = (int) -1e8;
for (int dj1 = -1; dj1 <= 1; dj1++) {
for (int dj2 = -1; dj2 <= 1; dj2++) {
int val = (j1 == j2)
? grid[row][j1]
: grid[row][j1] + grid[row][j2];
val += solve(row + 1, j1 + dj1, j2 + dj2,
R, C, grid);
maxVal = Math.max(maxVal, val);
}
}
return maxVal;
}
public int maximumChocolates(int R, int C,
int[][] grid) {
return solve(0, 0, C - 1, R, C, grid);
}
}Complexity Analysis
Time Complexity: O(9^R)
At each of the R rows, both Alice and Bob have up to 3 directional choices, giving 9 combinations per level. The recursion tree has depth R and branching factor up to 9, resulting in up to 9^R total calls. For R = 50, this is astronomically large — roughly 5 × 10^47 operations.
Space Complexity: O(R)
The recursion stack has depth R (one frame per row). No additional data structures are used beyond the call stack.
Why This Approach Is Not Efficient
The brute force explores an exponential number of recursive paths. The root cause is overlapping subproblems: many different paths from earlier rows lead to the same (row, j1, j2) state, but the brute force recomputes each one from scratch every time.
For example, in our trace, solve(2, 1, 3) was computed twice — once as a child of solve(1, 0, 2) and again as a child of solve(1, 1, 3). In a 50 × 50 grid, the state space is only R × C × C = 50 × 50 × 50 = 125,000 unique states, but the brute force may visit billions of paths through those states.
The fix is simple: if we store the result of each (row, j1, j2) state the first time we compute it, we can look it up instantly on subsequent visits. This is memoization, and it reduces the time from exponential O(9^R) to polynomial O(R × C²).
Better Approach - Memoization (Top-Down DP)
Intuition
The brute force already has the correct recursive structure — the only problem is redundant work. Memoization solves this by adding a simple cache: before computing any state (row, j1, j2), we first check if we have already computed and stored the result. If yes, return it immediately. If no, compute it, store the result, then return.
The state space has at most R × C × C = R × C² distinct states. Each state is computed exactly once and each computation examines at most 9 transitions — giving a total of O(R × C² × 9) = O(R × C²) time.
We use a 3D array memo[row][j1][j2] initialized to -1 (meaning "not yet computed"). When a result is computed, we store it in the array. On future lookups, if the value is not -1, we return it directly without recursing.
Step-by-Step Explanation
Using the same grid = [[2, 3, 1, 2], [3, 4, 2, 2], [5, 6, 3, 5]]:
Step 1: Call solve(0, 0, 3). Collect 2+2=4. Memo is empty. Branch to children.
Step 2: Explore solve(1, 0, 2). Collect 3+2=5. Not in memo. Expand children.
Step 3: solve(2, 0, 1): Base case = 5+6=11. Store memo[(2,0,1)] = 11.
Step 4: solve(2, 1, 3): Base case = 6+5=11. Store memo[(2,1,3)] = 11.
Step 5: solve(1, 0, 2) resolves: best child=11, total=5+11=16. Store memo[(1,0,2)] = 16.
Step 6: Now explore solve(1, 1, 3). Collect 4+2=6. Not in memo. Expand children.
Step 7: solve(1, 1, 3) needs solve(2, 1, 3). Check memo → FOUND! memo[(2,1,3)] = 11. Return immediately without recomputing. This is the key savings.
Step 8: solve(1, 1, 3) resolves: best child=11, total=6+11=17. Store memo[(1,1,3)] = 17.
Step 9: Root compares: solve(1,0,2)=16 vs solve(1,1,3)=17. Best=17.
Step 10: Final answer: 4+17 = 21. Same answer as brute force, but we avoided recomputing solve(2,1,3) and many other states.
Memoization — Cache Hits Prevent Redundant Work — Watch how storing computed results in a memo table lets us skip recomputation. When solve(2,1,3) is needed a second time, the memo returns the answer instantly.
Algorithm
- Create a 3D memo array
memo[R][C][C]initialized to -1 - Define
solve(row, j1, j2):- If out of bounds, return -∞
- If last row, return chocolates at current positions
- If
memo[row][j1][j2] ≠ -1, returnmemo[row][j1][j2](cache hit) - Compute: try all 9 direction combinations, take the max
- Store result in
memo[row][j1][j2]before returning
- Answer:
solve(0, 0, C - 1)
Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(int row, int j1, int j2, int R, int C,
vector<vector<int>>& grid,
vector<vector<vector<int>>>& memo) {
if (j1 < 0 || j1 >= C || j2 < 0 || j2 >= C)
return -1e8;
if (row == R - 1) {
if (j1 == j2) return grid[row][j1];
return grid[row][j1] + grid[row][j2];
}
if (memo[row][j1][j2] != -1)
return memo[row][j1][j2];
int maxVal = -1e8;
for (int dj1 = -1; dj1 <= 1; dj1++) {
for (int dj2 = -1; dj2 <= 1; dj2++) {
int val = (j1 == j2)
? grid[row][j1]
: grid[row][j1] + grid[row][j2];
val += solve(row + 1, j1 + dj1, j2 + dj2,
R, C, grid, memo);
maxVal = max(maxVal, val);
}
}
return memo[row][j1][j2] = maxVal;
}
int maximumChocolates(int R, int C,
vector<vector<int>>& grid) {
vector<vector<vector<int>>> memo(
R, vector<vector<int>>(C, vector<int>(C, -1)));
return solve(0, 0, C - 1, R, C, grid, memo);
}
};class Solution:
def maximumChocolates(self, R: int, C: int,
grid: list[list[int]]) -> int:
memo = {}
def solve(row, j1, j2):
if j1 < 0 or j1 >= C or j2 < 0 or j2 >= C:
return float('-inf')
if row == R - 1:
if j1 == j2:
return grid[row][j1]
return grid[row][j1] + grid[row][j2]
if (row, j1, j2) in memo:
return memo[(row, j1, j2)]
max_val = float('-inf')
for dj1 in range(-1, 2):
for dj2 in range(-1, 2):
val = grid[row][j1] if j1 == j2 \
else grid[row][j1] + grid[row][j2]
val += solve(row + 1, j1 + dj1, j2 + dj2)
max_val = max(max_val, val)
memo[(row, j1, j2)] = max_val
return max_val
return solve(0, 0, C - 1)import java.util.Arrays;
class Solution {
int[][][] memo;
int solve(int row, int j1, int j2, int R, int C,
int[][] grid) {
if (j1 < 0 || j1 >= C || j2 < 0 || j2 >= C)
return (int) -1e8;
if (row == R - 1) {
if (j1 == j2) return grid[row][j1];
return grid[row][j1] + grid[row][j2];
}
if (memo[row][j1][j2] != -1)
return memo[row][j1][j2];
int maxVal = (int) -1e8;
for (int dj1 = -1; dj1 <= 1; dj1++) {
for (int dj2 = -1; dj2 <= 1; dj2++) {
int val = (j1 == j2)
? grid[row][j1]
: grid[row][j1] + grid[row][j2];
val += solve(row + 1, j1 + dj1, j2 + dj2,
R, C, grid);
maxVal = Math.max(maxVal, val);
}
}
return memo[row][j1][j2] = maxVal;
}
public int maximumChocolates(int R, int C,
int[][] grid) {
memo = new int[R][C][C];
for (int[][] layer : memo)
for (int[] row : layer)
Arrays.fill(row, -1);
return solve(0, 0, C - 1, R, C, grid);
}
}Complexity Analysis
Time Complexity: O(R × C²)
There are R × C × C = R × C² unique states. Each state is computed exactly once (subsequent calls are O(1) memo lookups). Each computation checks 9 transitions. Total: O(R × C² × 9) = O(R × C²). For R = C = 50, this is 50 × 2500 × 9 = 1,125,000 operations — well within time limits.
Space Complexity: O(R × C²)
The memo table has R × C × C entries. Additionally, the recursion stack has depth R. Total space: O(R × C²) + O(R) = O(R × C²).
Why This Approach Is Not Efficient
Memoization achieves optimal O(R × C²) time, but it uses O(R × C²) space for the 3D memo table. For R = C = 50, this is 125,000 entries — manageable. But the space could be a concern for tighter constraints or when memory is limited.
The key observation is that each row's computation depends only on the next row's results (or the previous row's, depending on direction). We never look two rows ahead. This means we don't need to keep the entire R-deep table — just two layers at a time: the "current row" and the "next row."
By switching from top-down recursion to bottom-up iteration (tabulation) and keeping only two 2D slices of size C × C, we can reduce the space from O(R × C²) to O(C²) while maintaining the same O(R × C²) time complexity.
Optimal Approach - Space Optimized Tabulation
Intuition
Instead of recursion with memoization, we iterate through the grid row by row from top to bottom. We maintain a 2D table prev[j1][j2] representing the best total chocolates when Alice is at column j1 and Bob is at column j2 after processing all rows up to the previous one.
For each new row, we create a fresh table curr[j1][j2]. For every valid (j1, j2) pair, we check all 9 possible previous positions (pj1, pj2) that could have led here (pj1 ∈ {j1-1, j1, j1+1}, pj2 ∈ {j2-1, j2, j2+1}). We take the best prev[pj1][pj2] and add the chocolates collected at the current row.
After processing each row, we discard prev and promote curr to become the new prev. This way, we only ever store two C × C tables — reducing space from O(R × C²) to O(C²).
The final answer is the maximum value in the last row's table across all (j1, j2) pairs.
Step-by-Step Explanation
Using grid = [[2, 3, 1, 2], [3, 4, 2, 2], [5, 6, 3, 5]] (R=3, C=4):
Step 1: Initialize. Only valid starting state: Alice at col 0, Bob at col 3. prev[0][3] = grid[0][0] + grid[0][3] = 2 + 2 = 4. All other entries are -∞.
Step 2: Process row 1. Try (j1=0, j2=2): Alice at (1,0), Bob at (1,2). Previous positions reaching here: pj1 ∈ {0,1} from col 0, pj2 ∈ {1,2,3} from col 2. Best prev with valid value: prev[0][3] = 4. Chocolates: 3+2=5. curr[0][2] = 4+5 = 9.
Step 3: Try (j1=0, j2=3): Chocolates = 3+2=5. Best prev reaching here: prev[0][3] = 4. curr[0][3] = 9.
Step 4: Try (j1=1, j2=2): Chocolates = 4+2=6. prev[0][3] = 4 is reachable (Alice from col 0→1, Bob from col 3→2). curr[1][2] = 4+6 = 10.
Step 5: Try (j1=1, j2=3): Chocolates = 4+2=6. Best prev: prev[0][3] = 4. curr[1][3] = 4+6 = 10. Best for row 1 is 10.
Step 6: Swap: prev = curr. Now process row 2.
Step 7: Try (j1=0, j2=3): Chocolates = 5+5=10. Best prev reaching here includes prev[1][3]=10. curr[0][3] = 10+10 = 20.
Step 8: Try (j1=1, j2=2): Chocolates = 6+3=9. Best prev reaching here includes prev[1][3]=10 or prev[0][2]=9. Best=10. curr[1][2] = 10+9 = 19.
Step 9: Try (j1=1, j2=3): Chocolates = 6+5=11. Best prev: prev[1][3]=10 or prev[0][3]=9. Best=10. curr[1][3] = 10+11 = 21.
Step 10: Try (j1=0, j2=1): Chocolates = 5+6=11. Best prev: prev[1][2]=10. curr[0][1] = 10+11 = 21.
Step 11: Scan the final table for the maximum: max across all (j1, j2) = 21.
Step 12: Result: 21. Optimal paths: Alice (0,0)→(1,1)→(2,1) collecting 12, Bob (0,3)→(1,3)→(2,3) collecting 9.
Tabulation — Filling the Grid Row by Row — Watch Alice (green) and Bob (blue) explore positions at each row. The algorithm tries all valid placement combinations and keeps the best total at each step.
Algorithm
- Create two 2D arrays
prev[C][C]andcurr[C][C], both initialized to -∞ - Base case:
prev[0][C-1] = grid[0][0] + grid[0][C-1](starting positions) - For each row from 1 to R-1:
- For each valid (j1, j2) pair:
- Compute chocolates:
grid[row][j1](+grid[row][j2]if j1 ≠ j2) - Check all 9 predecessor positions (pj1, pj2) where pj1 ∈ {j1-1, j1, j1+1} and pj2 ∈ {j2-1, j2, j2+1}
curr[j1][j2] = max(prev[pj1][pj2]) + chocolates
- Compute chocolates:
- Swap:
prev = curr, resetcurr
- For each valid (j1, j2) pair:
- Answer: maximum value across all entries in
prev
Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximumChocolates(int R, int C,
vector<vector<int>>& grid) {
vector<vector<int>> prev(C, vector<int>(C, (int)-1e8));
vector<vector<int>> curr(C, vector<int>(C, (int)-1e8));
// Base case: row 0
prev[0][C - 1] = grid[0][0] + grid[0][C - 1];
for (int row = 1; row < R; row++) {
for (int j1 = 0; j1 < C; j1++) {
for (int j2 = 0; j2 < C; j2++) {
int chocolates = grid[row][j1];
if (j1 != j2)
chocolates += grid[row][j2];
int best = (int)-1e8;
for (int dj1 = -1; dj1 <= 1; dj1++) {
for (int dj2 = -1; dj2 <= 1; dj2++) {
int pj1 = j1 + dj1;
int pj2 = j2 + dj2;
if (pj1 >= 0 && pj1 < C &&
pj2 >= 0 && pj2 < C) {
best = max(best, prev[pj1][pj2]);
}
}
}
if (best > (int)-1e8)
curr[j1][j2] = best + chocolates;
}
}
prev = curr;
for (auto& row : curr)
fill(row.begin(), row.end(), (int)-1e8);
}
int ans = 0;
for (int j1 = 0; j1 < C; j1++)
for (int j2 = 0; j2 < C; j2++)
ans = max(ans, prev[j1][j2]);
return ans;
}
};class Solution:
def maximumChocolates(self, R: int, C: int,
grid: list[list[int]]) -> int:
NEG_INF = float('-inf')
prev = [[NEG_INF] * C for _ in range(C)]
# Base case: row 0
prev[0][C - 1] = grid[0][0] + grid[0][C - 1]
for row in range(1, R):
curr = [[NEG_INF] * C for _ in range(C)]
for j1 in range(C):
for j2 in range(C):
chocolates = grid[row][j1]
if j1 != j2:
chocolates += grid[row][j2]
best = NEG_INF
for dj1 in range(-1, 2):
for dj2 in range(-1, 2):
pj1 = j1 + dj1
pj2 = j2 + dj2
if 0 <= pj1 < C and 0 <= pj2 < C:
best = max(best, prev[pj1][pj2])
if best != NEG_INF:
curr[j1][j2] = best + chocolates
prev = curr
result = 0
for j1 in range(C):
for j2 in range(C):
result = max(result, prev[j1][j2])
return resultimport java.util.Arrays;
class Solution {
public int maximumChocolates(int R, int C,
int[][] grid) {
int NEG_INF = (int) -1e8;
int[][] prev = new int[C][C];
int[][] curr = new int[C][C];
for (int[] row : prev) Arrays.fill(row, NEG_INF);
prev[0][C - 1] = grid[0][0] + grid[0][C - 1];
for (int row = 1; row < R; row++) {
for (int[] r : curr) Arrays.fill(r, NEG_INF);
for (int j1 = 0; j1 < C; j1++) {
for (int j2 = 0; j2 < C; j2++) {
int chocolates = grid[row][j1];
if (j1 != j2)
chocolates += grid[row][j2];
int best = NEG_INF;
for (int dj1 = -1; dj1 <= 1; dj1++) {
for (int dj2 = -1; dj2 <= 1; dj2++) {
int pj1 = j1 + dj1;
int pj2 = j2 + dj2;
if (pj1 >= 0 && pj1 < C &&
pj2 >= 0 && pj2 < C) {
best = Math.max(best,
prev[pj1][pj2]);
}
}
}
if (best > NEG_INF)
curr[j1][j2] = best + chocolates;
}
}
int[][] temp = prev;
prev = curr;
curr = temp;
}
int ans = 0;
for (int j1 = 0; j1 < C; j1++)
for (int j2 = 0; j2 < C; j2++)
ans = Math.max(ans, prev[j1][j2]);
return ans;
}
}Complexity Analysis
Time Complexity: O(R × C²)
We iterate through R rows. For each row, we examine C × C position pairs. For each pair, we check 9 predecessor combinations. Total: R × C² × 9 = O(R × C²). Same time as memoization.
Space Complexity: O(C²)
We maintain only two 2D arrays of size C × C (prev and curr). After each row, we swap them — the old prev is discarded. This is a significant improvement over the O(R × C²) space used by memoization. For C = 50, we use just 2 × 2500 = 5000 integers instead of 125,000.