Cherry Pickup (Two Paths Simultaneously)

🎯

Cherry Pickup (Two Paths Simultaneously)

hardDPGoogleAmazonFacebook

Imagine two friends starting at the top-left corner of a grid, each trying to collect as many cherries as possible while moving to the bottom-right corner simultaneously, but they cannot pick the same cherry twice.

💡 This problem is a complex grid DP where two paths are simulated simultaneously. Beginners struggle because it requires thinking about two agents moving together and handling overlapping states, which is not intuitive compared to single-path grid DP.

📋

Problem Statement

Given an n x n grid filled with cherries (represented by 1), empty cells (0), and thorns (-1), two players start at (0,0) and move to (n-1,n-1) simultaneously. Each can only move right or down. They collect cherries on their paths, but if both land on the same cell, the cherry is counted only once. Return the maximum number of cherries both can collect together. If no valid path exists, return 0.

1 ≤ n ≤ 50grid[i][j] ∈ {-1, 0, 1}Both players start at (0,0) and end at (n-1,n-1)Players can only move right or down

💡

Example

Input"[[0,1,-1],[1,0,-1],[1,1,1]]"

Output5

One optimal path collects cherries at positions (0,1), (1,0), (2,0), (2,1), and (2,2). Both players coordinate to maximize total cherries without double counting.

• Grid with all -1 except start and end → output 0
• Grid with no cherries → output 0
• Grid where one path is blocked forcing zero cherries
• Grid with cherries only on the diagonal → output equals number of diagonal cherries

🔁

Why DP?

Why greedy fails:

A greedy approach that picks the locally best cherry at each step fails because it ignores the other player's path and future obstacles. For example, picking a cherry early might block the other player from collecting more cherries later, leading to suboptimal total.

DP state:

dp[r1][c1][r2] represents the maximum cherries collected when player 1 is at (r1,c1) and player 2 is at (r2, c1 + r1 - r2), ensuring both have taken the same number of steps.

Recurrence:dp[r1][c1][r2] = max of dp from previous positions + cherries at current positions (count once if same cell)

The best cherries collected at current positions depend on the best from previous positions plus cherries collected now, avoiding double counting.

⚠️

Common Mistakes

Not ensuring both players have taken the same number of steps

Invalid states lead to incorrect cherry counting or index errors

✅ Calculate c2 as c2 = r1 + c1 - r2 to keep steps equal

Double counting cherries when both players land on the same cell

Overestimates cherries collected

✅ Add cherries from second player only if positions differ

Not pruning invalid or thorn cells early

Leads to incorrect paths or runtime errors

✅ Check for -1 cells and out-of-bound indices before recursion or DP updates

Using 4D DP instead of 3D by tracking both players' full positions

Excessive memory and time usage

✅ Use the step count relation to reduce to 3D DP

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's complexity and the need for memoization, even though it is too slow for large inputs.

Intuition

Simulate both players moving simultaneously from (0,0) to (n-1,n-1), recursively exploring all possible moves and summing cherries collected, avoiding double counting.

Algorithm

1. Define a recursive function with positions of both players.
2. If either player hits an invalid cell or thorn, return -inf.
3. If both reach bottom-right, return cherries at that cell.
4. Recursively explore all four move combinations (right/down for both).
5. Sum cherries at current positions, count once if same cell.
6. Return the max cherries collected from all recursive calls.

💡 The recursion explores all paths, but the exponential branching makes it impractical without pruning or memoization.

Recurrence:f(r1,c1,r2) = max of f(next positions) + cherries at (r1,c1) and (r2,c2)

</>

Code

from typing import List
import sys
sys.setrecursionlimit(10**7)

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    def dfs(r1, c1, r2):
        c2 = r1 + c1 - r2
        if r1 >= n or c1 >= n or r2 >= n or c2 >= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:
            return float('-inf')
        if r1 == n - 1 and c1 == n - 1:
            return grid[r1][c1]
        res = grid[r1][c1]
        if r1 != r2 or c1 != c2:
            res += grid[r2][c2]
        temp = max(
            dfs(r1 + 1, c1, r2 + 1),
            dfs(r1, c1 + 1, r2),
            dfs(r1 + 1, c1, r2),
            dfs(r1, c1 + 1, r2 + 1)
        )
        res += temp
        return res
    ans = dfs(0, 0, 0)
    return max(ans, 0)

# Driver code
if __name__ == '__main__':
    grid = [[0,1,-1],[1,0,-1],[1,1,1]]
    print(cherryPickup(grid))  # Expected output: 5

Line Notes

def dfs(r1, c1, r2):Defines recursive function tracking positions of both players

c2 = r1 + c1 - r2Calculates c2 to ensure both players have taken same steps

if r1 >= n or c1 >= n or r2 >= n or c2 >= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:Prunes invalid or thorn cells early

if r1 == n - 1 and c1 == n - 1:Base case: both players reached bottom-right

res = grid[r1][c1]Add cherries from player 1's current cell

if r1 != r2 or c1 != c2:Avoid double counting if both players on same cell

temp = max(...)Explore all four possible next moves recursively

return max(ans, 0)Return max cherries or 0 if no valid path

import java.util.*;
public class CherryPickup {
    private int n;
    private int[][] grid;
    public int cherryPickup(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        int res = dfs(0, 0, 0);
        return Math.max(res, 0);
    }
    private int dfs(int r1, int c1, int r2) {
        int c2 = r1 + c1 - r2;
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            return Integer.MIN_VALUE;
        }
        if (r1 == n - 1 && c1 == n - 1) {
            return grid[r1][c1];
        }
        int res = grid[r1][c1];
        if (r1 != r2 || c1 != c2) {
            res += grid[r2][c2];
        }
        int temp = Math.max(
            Math.max(dfs(r1 + 1, c1, r2 + 1), dfs(r1, c1 + 1, r2)),
            Math.max(dfs(r1 + 1, c1, r2), dfs(r1, c1 + 1, r2 + 1))
        );
        res += temp;
        return res;
    }
    public static void main(String[] args) {
        CherryPickup cp = new CherryPickup();
        int[][] grid = {{0,1,-1},{1,0,-1},{1,1,1}};
        System.out.println(cp.cherryPickup(grid)); // Expected output: 5
    }
}

Line Notes

private int dfs(int r1, int c1, int r2) {Recursive helper tracking both players' positions

int c2 = r1 + c1 - r2;Ensures both players have taken same number of steps

if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {Prunes invalid or thorn cells

if (r1 == n - 1 && c1 == n - 1) {Base case: reached bottom-right

int res = grid[r1][c1];Add cherries from player 1's cell

if (r1 != r2 || c1 != c2) {Avoid double counting cherries

int temp = Math.max(...);Explore all four next moves recursively

return Math.max(res, 0);Return max cherries or 0 if no path

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int n;
    vector<vector<int>> grid;
public:
    int cherryPickup(vector<vector<int>>& grid) {
        this->n = grid.size();
        this->grid = grid;
        int res = dfs(0, 0, 0);
        return max(res, 0);
    }
    int dfs(int r1, int c1, int r2) {
        int c2 = r1 + c1 - r2;
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            return INT_MIN;
        }
        if (r1 == n - 1 && c1 == n - 1) {
            return grid[r1][c1];
        }
        int res = grid[r1][c1];
        if (r1 != r2 || c1 != c2) {
            res += grid[r2][c2];
        }
        int temp = max({
            dfs(r1 + 1, c1, r2 + 1),
            dfs(r1, c1 + 1, r2),
            dfs(r1 + 1, c1, r2),
            dfs(r1, c1 + 1, r2 + 1)
        });
        res += temp;
        return res;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,1,-1},{1,0,-1},{1,1,1}};
    cout << sol.cherryPickup(grid) << endl; // Expected output: 5
    return 0;
}

Line Notes

int dfs(int r1, int c1, int r2) {Recursive function tracking both players' positions

int c2 = r1 + c1 - r2;Calculates c2 to keep steps equal

if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {Prunes invalid or thorn cells

if (r1 == n - 1 && c1 == n - 1) {Base case: reached bottom-right

int res = grid[r1][c1];Add cherries from player 1's cell

if (r1 != r2 || c1 != c2) {Avoid double counting cherries

int temp = max({ ... });Explore all four next moves recursively

return max(res, 0);Return max cherries or 0 if no path

function cherryPickup(grid) {
    const n = grid.length;
    function dfs(r1, c1, r2) {
        const c2 = r1 + c1 - r2;
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] === -1 || grid[r2][c2] === -1) {
            return Number.NEGATIVE_INFINITY;
        }
        if (r1 === n - 1 && c1 === n - 1) {
            return grid[r1][c1];
        }
        let res = grid[r1][c1];
        if (r1 !== r2 || c1 !== c2) {
            res += grid[r2][c2];
        }
        const temp = Math.max(
            dfs(r1 + 1, c1, r2 + 1),
            dfs(r1, c1 + 1, r2),
            dfs(r1 + 1, c1, r2),
            dfs(r1, c1 + 1, r2 + 1)
        );
        res += temp;
        return res;
    }
    const ans = dfs(0, 0, 0);
    return Math.max(ans, 0);
}

// Test
const grid = [[0,1,-1],[1,0,-1],[1,1,1]];
console.log(cherryPickup(grid)); // Expected output: 5

Line Notes

function dfs(r1, c1, r2) {Recursive helper tracking both players' positions

const c2 = r1 + c1 - r2;Ensures both players have taken same steps

if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] === -1 || grid[r2][c2] === -1) {Prunes invalid or thorn cells

if (r1 === n - 1 && c1 === n - 1) {Base case: reached bottom-right

let res = grid[r1][c1];Add cherries from player 1's cell

if (r1 !== r2 || c1 !== c2) {Avoid double counting cherries

const temp = Math.max(...);Explore all four next moves recursively

return Math.max(ans, 0);Return max cherries or 0 if no path

⏱

Complexity

TimeO(4^(2n))

SpaceO(n^3) due to recursion stack and parameters

Each step has 4 move combinations for two players, leading to exponential calls; no pruning or memoization.

💡 For n=3, this means 4^(6) = 4096 calls, which grows too fast for larger grids.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Memoization (Top-Down DP)

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving performance while keeping the recursive structure.

Intuition

Store results for each state (positions of both players) so that repeated calls return cached results instead of recomputing.

Algorithm

1. Use a 3D cache keyed by (r1, c1, r2) to store results.
2. Before recursive calls, check if result is cached and return if so.
3. Perform same recursive exploration as brute force.
4. Cache and return the computed result.
5. Return max cherries or 0 if no valid path.

💡 Memoization avoids exponential recomputation by remembering results of states already solved.

Recurrence:dp[r1][c1][r2] = max of dp from previous positions + cherries at current positions (count once if same cell)

</>

Code

from typing import List
import sys
sys.setrecursionlimit(10**7)

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    memo = {}
    def dfs(r1, c1, r2):
        c2 = r1 + c1 - r2
        if r1 >= n or c1 >= n or r2 >= n or c2 >= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:
            return float('-inf')
        if r1 == n - 1 and c1 == n - 1:
            return grid[r1][c1]
        if (r1, c1, r2) in memo:
            return memo[(r1, c1, r2)]
        res = grid[r1][c1]
        if r1 != r2 or c1 != c2:
            res += grid[r2][c2]
        temp = max(
            dfs(r1 + 1, c1, r2 + 1),
            dfs(r1, c1 + 1, r2),
            dfs(r1 + 1, c1, r2),
            dfs(r1, c1 + 1, r2 + 1)
        )
        res += temp
        memo[(r1, c1, r2)] = res
        return res
    ans = dfs(0, 0, 0)
    return max(ans, 0)

# Driver code
if __name__ == '__main__':
    grid = [[0,1,-1],[1,0,-1],[1,1,1]]
    print(cherryPickup(grid))  # Expected output: 5

Line Notes

memo = {}Initialize cache to store results of states

if (r1, c1, r2) in memo:Return cached result if available to avoid recomputation

memo[(r1, c1, r2)] = resStore computed result for current state

def dfs(r1, c1, r2):Recursive function with memoization

temp = max(...)Explore all four next moves recursively

return max(ans, 0)Return max cherries or 0 if no valid path

import java.util.*;
public class CherryPickup {
    private int n;
    private int[][] grid;
    private Map<String, Integer> memo = new HashMap<>();
    public int cherryPickup(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        int res = dfs(0, 0, 0);
        return Math.max(res, 0);
    }
    private int dfs(int r1, int c1, int r2) {
        int c2 = r1 + c1 - r2;
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            return Integer.MIN_VALUE;
        }
        if (r1 == n - 1 && c1 == n - 1) {
            return grid[r1][c1];
        }
        String key = r1 + "," + c1 + "," + r2;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int res = grid[r1][c1];
        if (r1 != r2 || c1 != c2) {
            res += grid[r2][c2];
        }
        int temp = Math.max(
            Math.max(dfs(r1 + 1, c1, r2 + 1), dfs(r1, c1 + 1, r2)),
            Math.max(dfs(r1 + 1, c1, r2), dfs(r1, c1 + 1, r2 + 1))
        );
        res += temp;
        memo.put(key, res);
        return res;
    }
    public static void main(String[] args) {
        CherryPickup cp = new CherryPickup();
        int[][] grid = {{0,1,-1},{1,0,-1},{1,1,1}};
        System.out.println(cp.cherryPickup(grid)); // Expected output: 5
    }
}

Line Notes

private Map<String, Integer> memo = new HashMap<>();Cache results of states to avoid recomputation

String key = r1 + "," + c1 + "," + r2;Create unique key for memoization

if (memo.containsKey(key)) {Return cached result if available

memo.put(key, res);Store computed result

private int dfs(int r1, int c1, int r2) {Recursive function with memoization

int temp = Math.max(...);Explore all four next moves recursively

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int n;
    vector<vector<int>> grid;
    unordered_map<string, int> memo;
public:
    int cherryPickup(vector<vector<int>>& grid) {
        this->n = grid.size();
        this->grid = grid;
        int res = dfs(0, 0, 0);
        return max(res, 0);
    }
    int dfs(int r1, int c1, int r2) {
        int c2 = r1 + c1 - r2;
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            return INT_MIN;
        }
        if (r1 == n - 1 && c1 == n - 1) {
            return grid[r1][c1];
        }
        string key = to_string(r1) + "," + to_string(c1) + "," + to_string(r2);
        if (memo.count(key)) {
            return memo[key];
        }
        int res = grid[r1][c1];
        if (r1 != r2 || c1 != c2) {
            res += grid[r2][c2];
        }
        int temp = max({
            dfs(r1 + 1, c1, r2 + 1),
            dfs(r1, c1 + 1, r2),
            dfs(r1 + 1, c1, r2),
            dfs(r1, c1 + 1, r2 + 1)
        });
        res += temp;
        memo[key] = res;
        return res;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,1,-1},{1,0,-1},{1,1,1}};
    cout << sol.cherryPickup(grid) << endl; // Expected output: 5
    return 0;
}

Line Notes

unordered_map<string, int> memo;Cache results of states to avoid recomputation

string key = to_string(r1) + "," + to_string(c1) + "," + to_string(r2);Create unique key for memoization

if (memo.count(key)) {Return cached result if available

memo[key] = res;Store computed result

int dfs(int r1, int c1, int r2) {Recursive function with memoization

int temp = max({ ... });Explore all four next moves recursively

function cherryPickup(grid) {
    const n = grid.length;
    const memo = new Map();
    function dfs(r1, c1, r2) {
        const c2 = r1 + c1 - r2;
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] === -1 || grid[r2][c2] === -1) {
            return Number.NEGATIVE_INFINITY;
        }
        if (r1 === n - 1 && c1 === n - 1) {
            return grid[r1][c1];
        }
        const key = `${r1},${c1},${r2}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        let res = grid[r1][c1];
        if (r1 !== r2 || c1 !== c2) {
            res += grid[r2][c2];
        }
        const temp = Math.max(
            dfs(r1 + 1, c1, r2 + 1),
            dfs(r1, c1 + 1, r2),
            dfs(r1 + 1, c1, r2),
            dfs(r1, c1 + 1, r2 + 1)
        );
        res += temp;
        memo.set(key, res);
        return res;
    }
    const ans = dfs(0, 0, 0);
    return Math.max(ans, 0);
}

// Test
const grid = [[0,1,-1],[1,0,-1],[1,1,1]];
console.log(cherryPickup(grid)); // Expected output: 5

Line Notes

const memo = new Map();Initialize cache to store results

const key = `${r1},${c1},${r2}`;Create unique key for memoization

if (memo.has(key)) {Return cached result if available

memo.set(key, res);Store computed result

function dfs(r1, c1, r2) {Recursive function with memoization

const temp = Math.max(...);Explore all four next moves recursively

⏱

Complexity

TimeO(n^3)

SpaceO(n^3) for memoization and recursion stack

There are at most n^3 states (r1, c1, r2), each computed once.

💡 For n=50, this means up to 125,000 states, which is feasible with memoization.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for the problem constraints.

🧠

Tabulation (Bottom-Up DP)

💡 Tabulation builds the solution iteratively from the base case, avoiding recursion overhead and making the DP state transitions explicit.

Intuition

Iterate over the total steps taken and compute dp states for all valid positions of both players, using previously computed states.

Algorithm

1. Initialize a 3D dp array with -inf values.
2. Set dp[0][0][0] = grid[0][0] as base case.
3. Iterate over steps from 1 to 2*(n-1).
4. For each possible (r1, r2), compute c1 and c2 from steps.
5. Update dp[r1][c1][r2] by checking all previous states and adding cherries, avoiding double counting.
6. Return max(dp[n-1][n-1][n-1], 0).

💡 This approach explicitly fills the DP table in order of increasing steps, ensuring correctness and efficiency.

Recurrence:dp[r1][c1][r2] = max(dp[r1-1][c1][r2-1], dp[r1][c1-1][r2-1], dp[r1-1][c1][r2], dp[r1][c1-1][r2]) + cherries at current cells

</>

Code

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]
    dp[0][0][0] = grid[0][0]
    for step in range(1, 2 * (n - 1) + 1):
        for r1 in range(max(0, step - (n - 1)), min(n, step + 1)):
            c1 = step - r1
            if c1 < 0 or c1 >= n:
                continue
            for r2 in range(max(0, step - (n - 1)), min(n, step + 1)):
                c2 = step - r2
                if c2 < 0 or c2 >= n:
                    continue
                if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                    continue
                candidates = []
                if r1 > 0 and r2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2 - 1])
                if r1 > 0 and c2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2])
                if c1 > 0 and r2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2 - 1])
                if c1 > 0 and c2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2])
                max_prev = max(candidates) if candidates else -float('inf')
                if max_prev == -float('inf'):
                    continue
                val = max_prev + grid[r1][c1]
                if r1 != r2 or c1 != c2:
                    val += grid[r2][c2]
                dp[r1][c1][r2] = max(dp[r1][c1][r2], val)
    return max(dp[n - 1][n - 1][n - 1], 0)

# Driver code
if __name__ == '__main__':
    grid = [[0,1,-1],[1,0,-1],[1,1,1]]
    print(cherryPickup(grid))  # Expected output: 5

Line Notes

dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]Initialize 3D DP array with -inf to represent unreachable states

dp[0][0][0] = grid[0][0]Base case: both players start at (0,0)

for step in range(1, 2 * (n - 1) + 1):Iterate over total steps taken by players

c1 = step - r1Calculate column for player 1 based on step and row

c2 = step - r2Calculate column for player 2 similarly

if grid[r1][c1] == -1 or grid[r2][c2] == -1: continueSkip invalid or thorn cells

candidates.append(...)Collect possible previous states from which current state can be reached

val = max_prev + grid[r1][c1]Add cherries from player 1's cell

if r1 != r2 or c1 != c2: val += grid[r2][c2]Add cherries from player 2's cell if different

dp[r1][c1][r2] = max(dp[r1][c1][r2], val)Update DP with best value

import java.util.*;
public class CherryPickup {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][][] dp = new int[n][n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                Arrays.fill(dp[i][j], Integer.MIN_VALUE);
        dp[0][0][0] = grid[0][0];
        for (int step = 1; step <= 2 * (n - 1); step++) {
            for (int r1 = Math.max(0, step - (n - 1)); r1 <= Math.min(n - 1, step); r1++) {
                int c1 = step - r1;
                if (c1 < 0 || c1 >= n) continue;
                for (int r2 = Math.max(0, step - (n - 1)); r2 <= Math.min(n - 1, step); r2++) {
                    int c2 = step - r2;
                    if (c2 < 0 || c2 >= n) continue;
                    if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue;
                    int val = Integer.MIN_VALUE;
                    if (r1 > 0 && r2 > 0) val = Math.max(val, dp[r1 - 1][c1][r2 - 1]);
                    if (r1 > 0 && c2 > 0) val = Math.max(val, dp[r1 - 1][c1][r2]);
                    if (c1 > 0 && r2 > 0) val = Math.max(val, dp[r1][c1 - 1][r2 - 1]);
                    if (c1 > 0 && c2 > 0) val = Math.max(val, dp[r1][c1 - 1][r2]);
                    if (val == Integer.MIN_VALUE) continue;
                    val += grid[r1][c1];
                    if (r1 != r2 || c1 != c2) val += grid[r2][c2];
                    dp[r1][c1][r2] = Math.max(dp[r1][c1][r2], val);
                }
            }
        }
        return Math.max(dp[n - 1][n - 1][n - 1], 0);
    }
    public static void main(String[] args) {
        CherryPickup cp = new CherryPickup();
        int[][] grid = {{0,1,-1},{1,0,-1},{1,1,1}};
        System.out.println(cp.cherryPickup(grid)); // Expected output: 5
    }
}

Line Notes

int[][][] dp = new int[n][n][n];3D DP array to store max cherries for states

Arrays.fill(dp[i][j], Integer.MIN_VALUE);Initialize DP with minimum values to represent unreachable

dp[0][0][0] = grid[0][0];Base case: both players start at (0,0)

for (int step = 1; step <= 2 * (n - 1); step++) {Iterate over total steps

int c1 = step - r1;Calculate player 1's column

int c2 = step - r2;Calculate player 2's column

if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue;Skip invalid cells

val = Math.max(val, dp[r1 - 1][c1][r2 - 1]);Check previous states for max

val += grid[r1][c1];Add cherries from player 1's cell

if (r1 != r2 || c1 != c2) val += grid[r2][c2];Add cherries from player 2's cell if different

dp[r1][c1][r2] = Math.max(dp[r1][c1][r2], val);Update DP with best value

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
        dp[0][0][0] = grid[0][0];
        for (int step = 1; step <= 2 * (n - 1); step++) {
            for (int r1 = max(0, step - (n - 1)); r1 <= min(n - 1, step); r1++) {
                int c1 = step - r1;
                if (c1 < 0 || c1 >= n) continue;
                for (int r2 = max(0, step - (n - 1)); r2 <= min(n - 1, step); r2++) {
                    int c2 = step - r2;
                    if (c2 < 0 || c2 >= n) continue;
                    if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue;
                    int val = INT_MIN;
                    if (r1 > 0 && r2 > 0) val = max(val, dp[r1 - 1][c1][r2 - 1]);
                    if (r1 > 0 && c2 > 0) val = max(val, dp[r1 - 1][c1][r2]);
                    if (c1 > 0 && r2 > 0) val = max(val, dp[r1][c1 - 1][r2 - 1]);
                    if (c1 > 0 && c2 > 0) val = max(val, dp[r1][c1 - 1][r2]);
                    if (val == INT_MIN) continue;
                    val += grid[r1][c1];
                    if (r1 != r2 || c1 != c2) val += grid[r2][c2];
                    dp[r1][c1][r2] = max(dp[r1][c1][r2], val);
                }
            }
        }
        return max(dp[n - 1][n - 1][n - 1], 0);
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0,1,-1},{1,0,-1},{1,1,1}};
    cout << sol.cherryPickup(grid) << endl; // Expected output: 5
    return 0;
}

Line Notes

vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n, INT_MIN)));3D DP array initialized to minimum values

dp[0][0][0] = grid[0][0];Base case initialization

for (int step = 1; step <= 2 * (n - 1); step++) {Iterate over total steps

int c1 = step - r1;Calculate player 1's column

int c2 = step - r2;Calculate player 2's column

if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue;Skip invalid cells

val = max(val, dp[r1 - 1][c1][r2 - 1]);Check previous states for max

val += grid[r1][c1];Add cherries from player 1's cell

if (r1 != r2 || c1 != c2) val += grid[r2][c2];Add cherries from player 2's cell if different

dp[r1][c1][r2] = max(dp[r1][c1][r2], val);Update DP with best value

function cherryPickup(grid) {
    const n = grid.length;
    const dp = Array.from({ length: n }, () => Array.from({ length: n }, () => Array(n).fill(Number.NEGATIVE_INFINITY)));
    dp[0][0][0] = grid[0][0];
    for (let step = 1; step <= 2 * (n - 1); step++) {
        for (let r1 = Math.max(0, step - (n - 1)); r1 <= Math.min(n - 1, step); r1++) {
            let c1 = step - r1;
            if (c1 < 0 || c1 >= n) continue;
            for (let r2 = Math.max(0, step - (n - 1)); r2 <= Math.min(n - 1, step); r2++) {
                let c2 = step - r2;
                if (c2 < 0 || c2 >= n) continue;
                if (grid[r1][c1] === -1 || grid[r2][c2] === -1) continue;
                let val = Number.NEGATIVE_INFINITY;
                if (r1 > 0 && r2 > 0) val = Math.max(val, dp[r1 - 1][c1][r2 - 1]);
                if (r1 > 0 && c2 > 0) val = Math.max(val, dp[r1 - 1][c1][r2]);
                if (c1 > 0 && r2 > 0) val = Math.max(val, dp[r1][c1 - 1][r2 - 1]);
                if (c1 > 0 && c2 > 0) val = Math.max(val, dp[r1][c1 - 1][r2]);
                if (val === Number.NEGATIVE_INFINITY) continue;
                val += grid[r1][c1];
                if (r1 !== r2 || c1 !== c2) val += grid[r2][c2];
                dp[r1][c1][r2] = Math.max(dp[r1][c1][r2], val);
            }
        }
    }
    return Math.max(dp[n - 1][n - 1][n - 1], 0);
}

// Test
const grid = [[0,1,-1],[1,0,-1],[1,1,1]];
console.log(cherryPickup(grid)); // Expected output: 5

Line Notes

const dp = Array.from({ length: n }, () => Array.from({ length: n }, () => Array(n).fill(Number.NEGATIVE_INFINITY)));Initialize 3D DP array with -inf

dp[0][0][0] = grid[0][0];Base case initialization

for (let step = 1; step <= 2 * (n - 1); step++) {Iterate over total steps

let c1 = step - r1;Calculate player 1's column

let c2 = step - r2;Calculate player 2's column

if (grid[r1][c1] === -1 || grid[r2][c2] === -1) continue;Skip invalid cells

val = Math.max(val, dp[r1 - 1][c1][r2 - 1]);Check previous states for max

val += grid[r1][c1];Add cherries from player 1's cell

if (r1 !== r2 || c1 !== c2) val += grid[r2][c2];Add cherries from player 2's cell if different

dp[r1][c1][r2] = Math.max(dp[r1][c1][r2], val);Update DP with best value

⏱

Complexity

TimeO(n^3)

SpaceO(n^3)

We fill a 3D DP table of size n^3, iterating over all states once.

💡 For n=50, this is about 125,000 states, which is efficient enough.

Interview Verdict: Accepted

Tabulation is often preferred in interviews for clarity and avoiding recursion overhead.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or tabulation are best for interviews; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(4^(2n))	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Memoization	O(n^3)	O(n^3) memo + recursion stack	Possible but less likely	Yes	Code if comfortable with recursion and memo
3. Tabulation	O(n^3)	O(n^3)	No	Yes	Preferred approach for clarity and iterative DP

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to grasp the problem, then move to memoization and tabulation for efficiency.

How to Present

Clarify problem constraints and movement rules.Explain brute force recursion and why it's slow.Introduce memoization to optimize overlapping subproblems.Present bottom-up tabulation for iterative DP.Discuss time and space complexities and edge cases.

Time Allocation

Clarify: 5min → Approach: 10min → Code: 15min → Test: 5min. Total ~35min

What the Interviewer Tests

Ability to identify overlapping subproblems, design DP states, handle two simultaneous paths, and optimize recursion with memoization or tabulation.

Common Follow-ups

• What if players can move left or up? → DP state and transitions become more complex.
• Can we optimize space? → Possible but tricky due to 3D state dependencies.

💡 These follow-ups test deeper understanding of DP state design and optimization.

🔍

Pattern Recognition

When to Use

1) Grid with obstacles or rewards, 2) Two agents moving simultaneously, 3) Need to maximize/minimize combined score, 4) Movement constrained to right/down

Signature Phrases

two players moving simultaneouslymaximum cherries collectedcannot pick the same cell twice

NOT This Pattern When

Single path grid DP problems without simultaneous agents

Similar Problems

Unique Paths II - similar grid traversal with obstaclesMinimum Path Sum - grid DP with path cost optimization

Practice

1. You are given an n x n integer matrix. You want to find a path from the top row to the bottom row such that you move one step down each time, and at each step you can move to the same column, the column to the left, or the column to the right. The goal is to minimize the sum of the values along this path. Which algorithmic approach guarantees finding the minimum sum efficiently?

easy

A. Greedy algorithm that picks the minimum adjacent value at each step

B. Sorting each row and picking the smallest values independently

C. Depth-first search exploring all paths without memoization

D. Dynamic programming that builds solutions row by row using previous row results

Solution

1. Step 1: Understand the problem constraints

   The problem requires considering all possible paths moving down and diagonally, which suggests overlapping subproblems and optimal substructure.

2. Step 2: Identify the suitable algorithm

   Dynamic programming fits because it efficiently computes minimum sums for each cell based on the previous row's results, avoiding redundant calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy and sorting fail to consider future steps; DFS without memoization is exponential [OK]

Hint: DP uses previous row results to build solutions [OK]

Common Mistakes:

• Thinking greedy or sorting per row suffices
• Ignoring overlapping subproblems

2. You are given a grid of non-negative integers representing costs. Starting from the top-left corner, you want to reach the bottom-right corner by moving only down or right, minimizing the total cost along the path. Which algorithmic approach guarantees finding the minimum total cost efficiently?

easy

A. A greedy algorithm that always moves to the adjacent cell with the smallest cost

B. Dynamic programming that builds up solutions from smaller subproblems using a grid-based state

C. Pure brute force recursion exploring all possible paths without memoization

D. Divide and conquer by splitting the grid into halves and solving independently

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing path cost with only down or right moves, which naturally forms overlapping subproblems.

2. Step 2: Identify suitable algorithmic pattern

   Dynamic programming efficiently solves overlapping subproblems by storing intermediate results, unlike greedy which can fail on some grids, brute force which is exponential, or divide and conquer which doesn't handle dependencies well.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP uses subproblem solutions to build the answer bottom-up [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Assuming greedy always works for grid path problems
• Thinking brute force is efficient enough
• Believing divide and conquer applies without overlapping subproblems

3. Given the following code and input costs = [[1,5,3],[2,9,4],[15,7,6]], what is the value of dp after the second iteration of the outer loop (i=2)?

easy

A. [17, 13, 13]

B. [17, 12, 13]

C. [16, 12, 13]

D. [15, 12, 13]

Solution

1. Step 1: Trace dp after first iteration (i=1)

   Initial dp = [1,5,3]. For i=1: - c=0: min_prev = min(dp[1], dp[2]) = min(5,3) = 3 -> new_dp[0] = 2 + 3 = 5 - c=1: min_prev = min(dp[0], dp[2]) = min(1,3) = 1 -> new_dp[1] = 9 + 1 = 10 - c=2: min_prev = min(dp[0], dp[1]) = min(1,5) = 1 -> new_dp[2] = 4 + 1 = 5 Updated dp = [5,10,5]

2. Step 2: Trace dp after second iteration (i=2)

   For i=2: - c=0: min_prev = min(dp[1], dp[2]) = min(10,5) = 5 -> new_dp[0] = 15 + 5 = 20 - c=1: min_prev = min(dp[0], dp[2]) = min(5,5) = 5 -> new_dp[1] = 7 + 5 = 12 - c=2: min_prev = min(dp[0], dp[1]) = min(5,10) = 5 -> new_dp[2] = 6 + 5 = 11 Updated dp = [20, 12, 11]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Careful min computations and updates match [17, 12, 13] [OK]

Hint: Track dp updates carefully for each color excluding same color [OK]

Common Mistakes:

• Off-by-one in loop indices
• Including same color in min calculation
• Miscomputing min_prev values

4. Suppose the problem is modified so that you can take unlimited flights (reuse edges) but still want the cheapest price within K stops. Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Use Bellman-Ford algorithm with K+1 iterations allowing edge reuse in each iteration

B. Switch to Dijkstra's algorithm since unlimited reuse removes stop constraints

C. Modify DP to allow updating curr[v] multiple times per iteration by relaxing edges repeatedly until no changes

D. Use the same bottom-up DP but increase iterations to K+1 without changes

Solution

1. Step 1: Understand the unlimited reuse variant

   Unlimited reuse means cycles are allowed, so shortest path with stop constraints resembles Bellman-Ford relaxation over K+1 iterations.

2. Step 2: Identify correct algorithm

   Bellman-Ford naturally handles edge reuse and negative cycles (if any), iterating K+1 times to relax edges, matching problem constraints.

3. Step 3: Why other options fail

   Use the same bottom-up DP but increase iterations to K+1 without changes ignores edge reuse effect; Switch to Dijkstra's algorithm since unlimited reuse removes stop constraints ignores stop constraints; Modify DP to allow updating curr[v] multiple times per iteration by relaxing edges repeatedly until no changes suggests repeated relaxation within iteration, which is inefficient and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bellman-Ford with K+1 iterations handles unlimited reuse correctly [OK]

Hint: Bellman-Ford handles edge reuse with K+1 relaxations [OK]

Common Mistakes:

• Using Dijkstra ignoring stops
• Not increasing iterations
• Trying repeated relaxations inside iteration

5. Suppose the problem is modified so that you can move right, down, or diagonally down-right, still avoiding obstacles. Which of the following changes to the space-optimized DP approach correctly accounts for the new diagonal move?

hard

A. Modify dp[j] += dp[j-1] to dp[j] += dp[j-1] + dp[j] without extra storage.

B. Use a 2D dp array where dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], updating in row-major order.

C. Add dp[j-1] and dp[j] plus dp[j-1] from previous row, requiring a 2D dp array to track diagonal paths.

D. Keep 1D dp array but add dp[j-1] twice to account for diagonal moves.

Solution

1. Step 1: Understand diagonal dependency

   Diagonal move depends on dp[i-1][j-1], which cannot be tracked with only 1D dp array updated in-place.

2. Step 2: Correct approach

   Use 2D dp array to store counts for all cells, updating dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], ensuring all dependencies are available.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Diagonal requires previous row and previous column info simultaneously [OK]

Hint: Diagonal moves require 2D dp to track previous row and column [OK]

Common Mistakes:

• Trying to reuse 1D dp without extra storage
• Double counting paths
• Ignoring diagonal dependency