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 a 2D grid representing a dungeon where each cell contains an integer indicating health points gained or lost upon entering. You start at the top-left and must reach the bottom-right cell, moving only right or down. Your health must never drop below 1 at any point. Which algorithmic approach guarantees finding the minimum initial health required to survive the dungeon?

easy

A. Dynamic programming starting from the bottom-right cell and moving backward to the top-left

B. Greedy algorithm that always chooses the next cell with the highest health gain

C. Pure brute force recursion exploring all paths from start to end

D. Dijkstra's shortest path algorithm treating health as distance

Solution

1. Step 1: Understand problem constraints

   The problem requires minimum initial health ensuring health never drops below 1, which depends on future cells, so greedy or shortest path won't work.

2. Step 2: Identify correct DP direction

   Starting from the bottom-right cell and moving backward allows computing minimum health needed at each cell based on future states.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backward DP correctly accounts for future health requirements [OK]

Hint: Backward DP from goal ensures future states known [OK]

Common Mistakes:

• Assuming greedy or forward DP works
• Using shortest path ignoring health constraints

2. What is the time complexity of the space-optimized bottom-up DP solution for the Cheapest Flights Within K Stops problem, given n cities, E flights, and maximum K stops?

medium

A. O(K * E) because each iteration relaxes all edges up to K+1 times

B. O(n^3) due to nested loops over cities and stops

C. O(E * log n) similar to Dijkstra's algorithm

D. O(n * K^2) due to dynamic programming over stops and cities

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop runs K+1 times, and the inner loop iterates over all E flights to relax edges.

2. Step 2: Calculate total complexity

   Each iteration processes E edges, so total time is O(K * E). No nested loops over n^2 or log factors appear.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Algorithm iterates over edges K+1 times [OK]

Hint: Outer loop K+1 times, inner loop over E edges [OK]

Common Mistakes:

• Confusing E with n^2
• Assuming Dijkstra complexity
• Counting recursion stack space

3. The following code attempts to solve the Triangle minimum path sum problem using bottom-up DP. Identify the line that contains a subtle bug causing incorrect results on some inputs.

medium

A. for i in range(len(triangle) - 2, -1, -1):

B. dp[j] = triangle[i][j] + min(dp[j + 1], dp[j])

C. dp = triangle[-1][:]

D. return dp[0]

Solution

1. Step 1: Examine dp update line

   The original code has dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]). The buggy code swaps the min arguments to min(dp[j + 1], dp[j]) which is harmless since min is commutative.

2. Step 2: Check for index out of bounds risk

   Accessing dp[j + 1] is safe because dp length is one more than current row length, so no out-of-bounds here.

3. Step 3: Identify subtle bug

   The subtle bug is that dp is updated in place from left to right, which can cause dp[j + 1] to be already updated when used in min, leading to incorrect results.

4. Step 4: Explanation of bug

   Because dp is updated from left to right, dp[j + 1] may have been updated in the current iteration, so min(dp[j], dp[j + 1]) uses a mixed state of dp values.

5. Step 5: Correct fix

   To fix, update dp from right to left so dp[j + 1] is not yet updated when used.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Updating dp in wrong order causes subtle bugs [OK]

Hint: Bug usually in dp update line with min or indexing [OK]

Common Mistakes:

• Swapping min arguments (harmless but suspicious)
• Index out of bounds on dp[j+1]
• Updating dp in wrong order causing overwritten values

4. What is the time and space complexity of the optimal space-optimized bottom-up DP solution for the Unique Paths II problem on an m x n grid with obstacles?

medium

A. Time: O(m*n), Space: O(m*n)

B. Time: O(m+n), Space: O(m+n)

C. Time: O(m*n), Space: O(n)

D. Time: O(2^(m+n)), Space: O(m*n)

Solution

1. Step 1: Analyze time complexity

   The algorithm iterates over each cell once in nested loops: O(m*n).

2. Step 2: Analyze space complexity

   Uses a single 1D dp array of length n, so space is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over m and n, dp array size n [OK]

Hint: Nested loops over m and n, dp array size n [OK]

Common Mistakes:

• Confusing recursion stack space with dp array
• Assuming full 2D dp array used
• Mistaking linear time for exponential

5. Suppose the Burst Balloons problem is modified so that each balloon can be burst multiple times (reused), and bursting a balloon again yields coins based on the current adjacent balloons. Which of the following changes to the bottom-up DP approach correctly adapts to this variant?

hard

A. Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts

B. Modify the DP to consider only the first burst of each balloon and ignore reuse

C. Use the same interval DP but allow k to be chosen multiple times per interval

D. Use a greedy approach bursting the balloon with the maximum product of neighbors repeatedly

Solution

1. Step 1: Understand reuse impact

   Allowing multiple bursts per balloon means the problem state must track how many times each balloon has been burst, increasing complexity.

2. Step 2: Adapt DP state

   Interval DP assuming each balloon bursts once no longer works. We need a DP or memoization that tracks burst counts per balloon to correctly compute coins.

3. Step 3: Evaluate options

   Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts correctly proposes a stateful DP with counts and memoization. Use the same interval DP but allow k to be chosen multiple times per interval incorrectly reuses interval DP without state changes. Modify the DP to consider only the first burst of each balloon and ignore reuse ignores reuse, and D is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking burst counts is necessary for reuse variants [OK]

Hint: Reuse requires tracking burst counts, not just intervals [OK]

Common Mistakes:

• Trying naive interval DP for reuse
• Ignoring state explosion
• Using greedy for complex DP variants