Cherry Pickup

Problem

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.

• 0 means the cell is empty, so you can pass through,
• 1 means the cell contains a cherry that you can pick up and pass through, or
• -1 means the cell contains a thorn that blocks your way.

Return the maximum number of cherries you can collect by following the rules below:

• Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1).
• After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells.
• When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0.
• If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.

Examples

Example 1

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.

Example 2

Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0

Constraints

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• grid[i][j] is -1, 0, or 1.
• grid[0][0] != -1
• grid[n - 1][n - 1] != -1

Solution

Method 1 – Top Down Dynamic Programming (Memoization)

Intuition

The problem can be transformed into finding the maximum cherries collected by two people starting from (0,0) and moving to (n-1,n-1) simultaneously, since the return trip is symmetric. At each step, both can move either right or down, and if they land on the same cell, only one cherry is picked. This allows us to use a 3D DP to represent the state.

Approach

1. Define a recursive function dp(r1, c1, r2) where:

• (r1, c1): position of person 1
• (r2, c2): position of person 2, with c2 = r1 + c1 - r2 (since both have taken the same number of steps)

2. At each step, check if either position is out of bounds or on a thorn (-1). If so, return negative infinity.
3. If both reach the bottom-right cell, return its value.
4. Collect cherries at both positions (avoid double-counting if both are at the same cell).
5. Recursively try all combinations of moves (down or right for both), and take the maximum.
6. Memoize results to avoid recomputation.
7. Return the maximum cherries collected, or 0 if no valid path exists.

Code

C++

class Solution {
public:
   int cherryPickup(vector<vector<int>>& grid) {
      int n = grid.size();
      vector<vector<vector<int>>> memo(n, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
      function<int(int,int,int)> dp = [&](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 -100000;
        if (r1 == n-1 && c1 == n-1)
           return grid[r1][c1];
        if (memo[r1][c1][r2] != INT_MIN)
           return memo[r1][c1][r2];
        int ans = grid[r1][c1];
        if (r1 != r2 || c1 != c2)
           ans += grid[r2][c2];
        int best = max({
           dp(r1+1, c1, r2+1),
           dp(r1, c1+1, r2),
           dp(r1+1, c1, r2),
           dp(r1, c1+1, r2+1)
        });
        ans += best;
        return memo[r1][c1][r2] = ans;
      };
      return max(0, dp(0,0,0));
   }
};

Go

func cherryPickup(grid [][]int) int {
   n := len(grid)
   memo := make([][][]int, n)
   for i := range memo {
      memo[i] = make([][]int, n)
      for j := range memo[i] {
        memo[i][j] = make([]int, n)
        for k := range memo[i][j] {
           memo[i][j][k] = -100000
        }
      }
   }
   var dp func(int, int, int) int
   dp = func(r1, c1, r2 int) int {
      c2 := r1 + c1 - r2
      if r1 >= n || c1 >= n || r2 >= n || c2 >= n ||
        grid[r1][c1] == -1 || grid[r2][c2] == -1 {
        return -100000
      }
      if r1 == n-1 && c1 == n-1 {
        return grid[r1][c1]
      }
      if memo[r1][c1][r2] != -100000 {
        return memo[r1][c1][r2]
      }
      ans := grid[r1][c1]
      if r1 != r2 || c1 != c2 {
        ans += grid[r2][c2]
      }
      best := max(
        dp(r1+1, c1, r2+1),
        dp(r1, c1+1, r2),
        dp(r1+1, c1, r2),
        dp(r1, c1+1, r2+1),
      )
      ans += best
      memo[r1][c1][r2] = ans
      return ans
   }
   res := dp(0, 0, 0)
   if res < 0 {
      return 0
   }
   return res
}

func max(a, b, c, d int) int {
   m := a
   if b > m { m = b }
   if c > m { m = c }
   if d > m { m = d }
   return m
}

Java

class Solution {
   public int cherryPickup(int[][] grid) {
      int n = grid.length;
      Integer[][][] memo = new Integer[n][n][n];
      return Math.max(0, dp(0, 0, 0, grid, memo));
   }
   private int dp(int r1, int c1, int r2, int[][] grid, Integer[][][] memo) {
      int n = grid.length;
      int c2 = r1 + c1 - r2;
      if (r1 >= n || c1 >= n || r2 >= n || c2 >= n ||
        grid[r1][c1] == -1 || grid[r2][c2] == -1)
        return -100000;
      if (r1 == n-1 && c1 == n-1)
        return grid[r1][c1];
      if (memo[r1][c1][r2] != null)
        return memo[r1][c1][r2];
      int ans = grid[r1][c1];
      if (r1 != r2 || c1 != c2)
        ans += grid[r2][c2];
      int best = Math.max(
        Math.max(dp(r1+1, c1, r2+1, grid, memo), dp(r1, c1+1, r2, grid, memo)),
        Math.max(dp(r1+1, c1, r2, grid, memo), dp(r1, c1+1, r2+1, grid, memo))
      );
      ans += best;
      memo[r1][c1][r2] = ans;
      return ans;
   }
}

Kotlin

class Solution {
   fun cherryPickup(grid: Array<IntArray>): Int {
      val n = grid.size
      val memo = Array(n) { Array(n) { IntArray(n) { Int.MIN_VALUE } } }
      fun dp(r1: Int, c1: Int, r2: Int): Int {
        val c2 = r1 + c1 - r2
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n ||
           grid[r1][c1] == -1 || grid[r2][c2] == -1) return -100000
        if (r1 == n-1 && c1 == n-1) return grid[r1][c1]
        if (memo[r1][c1][r2] != Int.MIN_VALUE) return memo[r1][c1][r2]
        var ans = grid[r1][c1]
        if (r1 != r2 || c1 != c2) ans += grid[r2][c2]
        val best = maxOf(
           dp(r1+1, c1, r2+1),
           dp(r1, c1+1, r2),
           dp(r1+1, c1, r2),
           dp(r1, c1+1, r2+1)
        )
        ans += best
        memo[r1][c1][r2] = ans
        return ans
      }
      return maxOf(0, dp(0, 0, 0))
   }
}

Python

class Solution:
   def cherryPickup(self, grid: list[list[int]]) -> int:
      n = len(grid)
      memo: dict[tuple[int, int, int], int] = {}
      def dp(r1: int, c1: int, r2: int) -> int:
        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 -100000
        if r1 == n-1 and c1 == n-1:
           return grid[r1][c1]
        if (r1, c1, r2) in memo:
           return memo[(r1, c1, r2)]
        ans = grid[r1][c1]
        if r1 != r2 or c1 != c2:
           ans += grid[r2][c2]
        best = max(
           dp(r1+1, c1, r2+1),
           dp(r1, c1+1, r2),
           dp(r1+1, c1, r2),
           dp(r1, c1+1, r2+1)
        )
        ans += best
        memo[(r1, c1, r2)] = ans
        return ans
      return max(0, dp(0, 0, 0))

Rust

impl Solution {
   pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
      let n = grid.len();
      let mut memo = vec![vec![vec![None; n]; n]; n];
      fn dp(r1: usize, c1: usize, r2: usize, grid: &Vec<Vec<i32>>, memo: &mut Vec<Vec<Vec<Option<i32>>>>) -> i32 {
        let n = grid.len();
        let c2 = r1 + c1 - r2;
        if r1 >= n || c1 >= n || r2 >= n || c2 >= n ||
           grid[r1][c1] == -1 || grid[r2][c2] == -1 {
           return -100000;
        }
        if r1 == n-1 && c1 == n-1 {
           return grid[r1][c1];
        }
        if let Some(val) = memo[r1][c1][r2] {
           return val;
        }
        let mut ans = grid[r1][c1];
        if r1 != r2 || c1 != c2 {
           ans += grid[r2][c2];
        }
        let mut best = dp(r1+1, c1, r2+1, grid, memo)
           .max(dp(r1, c1+1, r2, grid, memo))
           .max(dp(r1+1, c1, r2, grid, memo))
           .max(dp(r1, c1+1, r2+1, grid, memo));
        ans += best;
        memo[r1][c1][r2] = Some(ans);
        ans
      }
      0.max(dp(0, 0, 0, &grid, &mut memo))
   }
}

Complexity

• ⏰ Time complexity: O(n^3) — Each state is defined by three variables, each up to n.
• 🧺 Space complexity: O(n^3) — For memoization storage.

Method 2 – Bottom Up Dynamic Programming

Intuition

Instead of using recursion and memoization, we can use an iterative approach to fill a 3D DP table. The key insight is that the two traversals (forward and backward) can be modeled as two people starting from (0,0) and moving to (n-1,n-1) simultaneously, and at each step, both can move either right or down. The DP state represents the maximum cherries collected when both are at certain positions after a given number of steps.

Approach

1. Let dp[k][i][j] be the maximum cherries collected when both persons have taken k steps, and are at positions (i, k-i) and (j, k-j) respectively.
2. Both persons start at (0,0). For each step k from 0 to 2n-2, iterate over all possible positions (i, k-i) and (j, k-j) that are within bounds and not on thorns.
3. For each state, consider all four ways the two persons could have arrived at their current positions (from left or above for each).
4. If both are at the same cell, only count the cherry once.
5. The answer is max(0, dp[2n-2][n-1][n-1]).

Code

C++

class Solution {
public:
  int cherryPickup(vector<vector<int>>& grid) {
    int n = grid.size();
    int maxK = 2 * n - 2;
    vector<vector<vector<int>>> dp(maxK + 1, vector<vector<int>>(n, vector<int>(n, -100000)));
    dp[0][0][0] = grid[0][0];
    for (int k = 1; k <= maxK; ++k) {
      for (int i = max(0, k - (n - 1)); i <= min(n - 1, k); ++i) {
        for (int j = max(0, k - (n - 1)); j <= min(n - 1, k); ++j) {
          int y1 = k - i, y2 = k - j;
          if (grid[i][y1] == -1 || grid[j][y2] == -1) continue;
          int val = grid[i][y1];
          if (i != j || y1 != y2) val += grid[j][y2];
          int best = -100000;
          for (int di = 0; di <= 1; ++di) {
            for (int dj = 0; dj <= 1; ++dj) {
              int pi = i - di, pj = j - dj;
              if (pi >= 0 && pj >= 0)
                best = max(best, dp[k - 1][pi][pj]);
            }
          }
          if (best > -100000)
            dp[k][i][j] = best + val;
        }
      }
    }
    return max(0, dp[maxK][n - 1][n - 1]);
  }
};

Go

func cherryPickup(grid [][]int) int {
  n := len(grid)
  maxK := 2*n - 2
  dp := make([][][]int, maxK+1)
  for k := range dp {
    dp[k] = make([][]int, n)
    for i := range dp[k] {
      dp[k][i] = make([]int, n)
      for j := range dp[k][i] {
        dp[k][i][j] = -100000
      }
    }
  }
  dp[0][0][0] = grid[0][0]
  for k := 1; k <= maxK; k++ {
    for i := maxInt(0, k-(n-1)); i <= minInt(n-1, k); i++ {
      for j := maxInt(0, k-(n-1)); j <= minInt(n-1, k); j++ {
        y1, y2 := k-i, k-j
        if grid[i][y1] == -1 || grid[j][y2] == -1 {
          continue
        }
        val := grid[i][y1]
        if i != j || y1 != y2 {
          val += grid[j][y2]
        }
        best := -100000
        for di := 0; di <= 1; di++ {
          for dj := 0; dj <= 1; dj++ {
            pi, pj := i-di, j-dj
            if pi >= 0 && pj >= 0 {
              if dp[k-1][pi][pj] > best {
                best = dp[k-1][pi][pj]
              }
            }
          }
        }
        if best > -100000 {
          dp[k][i][j] = best + val
        }
      }
    }
  }
  if dp[maxK][n-1][n-1] < 0 {
    return 0
  }
  return dp[maxK][n-1][n-1]
}

func maxInt(a, b int) int {
  if a > b {
    return a
  }
  return b
}
func minInt(a, b int) int {
  if a < b {
    return a
  }
  return b
}

Java

class Solution {
  public int cherryPickup(int[][] grid) {
    int n = grid.length;
    int maxK = 2 * n - 2;
    int[][][] dp = new int[maxK + 1][n][n];
    for (int k = 0; k <= maxK; k++)
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
          dp[k][i][j] = -100000;
    dp[0][0][0] = grid[0][0];
    for (int k = 1; k <= maxK; k++) {
      for (int i = Math.max(0, k - (n - 1)); i <= Math.min(n - 1, k); i++) {
        for (int j = Math.max(0, k - (n - 1)); j <= Math.min(n - 1, k); j++) {
          int y1 = k - i, y2 = k - j;
          if (grid[i][y1] == -1 || grid[j][y2] == -1) continue;
          int val = grid[i][y1];
          if (i != j || y1 != y2) val += grid[j][y2];
          int best = -100000;
          for (int di = 0; di <= 1; di++) {
            for (int dj = 0; dj <= 1; dj++) {
              int pi = i - di, pj = j - dj;
              if (pi >= 0 && pj >= 0)
                best = Math.max(best, dp[k - 1][pi][pj]);
            }
          }
          if (best > -100000)
            dp[k][i][j] = best + val;
        }
      }
    }
    return Math.max(0, dp[maxK][n - 1][n - 1]);
  }
}

Kotlin

class Solution {
  fun cherryPickup(grid: Array<IntArray>): Int {
    val n = grid.size
    val maxK = 2 * n - 2
    val dp = Array(maxK + 1) { Array(n) { IntArray(n) { -100000 } } }
    dp[0][0][0] = grid[0][0]
    for (k in 1..maxK) {
      for (i in maxOf(0, k - (n - 1))..minOf(n - 1, k)) {
        for (j in maxOf(0, k - (n - 1))..minOf(n - 1, k)) {
          val y1 = k - i
          val y2 = k - j
          if (grid[i][y1] == -1 || grid[j][y2] == -1) continue
          var v = grid[i][y1]
          if (i != j || y1 != y2) v += grid[j][y2]
          var best = -100000
          for (di in 0..1) {
            for (dj in 0..1) {
              val pi = i - di
              val pj = j - dj
              if (pi >= 0 && pj >= 0)
                best = maxOf(best, dp[k - 1][pi][pj])
            }
          }
          if (best > -100000)
            dp[k][i][j] = best + v
        }
      }
    }
    return maxOf(0, dp[maxK][n - 1][n - 1])
  }
}

Python

class Solution:
  def cherryPickup(self, grid: list[list[int]]) -> int:
    n: int = len(grid)
    max_k: int = 2 * n - 2
    dp: list[list[list[int]]] = [[[-100000] * n for _ in range(n)] for _ in range(max_k + 1)]
    dp[0][0][0] = grid[0][0]
    for k in range(1, max_k + 1):
      for i in range(max(0, k - (n - 1)), min(n - 1, k) + 1):
        for j in range(max(0, k - (n - 1)), min(n - 1, k) + 1):
          y1, y2 = k - i, k - j
          if grid[i][y1] == -1 or grid[j][y2] == -1:
            continue
          val = grid[i][y1]
          if i != j or y1 != y2:
            val += grid[j][y2]
          best = -100000
          for di in (0, 1):
            for dj in (0, 1):
              pi, pj = i - di, j - dj
              if pi >= 0 and pj >= 0:
                best = max(best, dp[k - 1][pi][pj])
          if best > -100000:
            dp[k][i][j] = best + val
    return max(0, dp[max_k][n - 1][n - 1])

Rust

impl Solution {
  pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
    let n = grid.len();
    let max_k = 2 * n - 2;
    let mut dp = vec![vec![vec![-100000; n]; n]; max_k + 1];
    dp[0][0][0] = grid[0][0];
    for k in 1..=max_k {
      for i in k.saturating_sub(n - 1)..=k.min(n - 1) {
        for j in k.saturating_sub(n - 1)..=k.min(n - 1) {
          let y1 = k - i;
          let y2 = k - j;
          if grid[i][y1] == -1 || grid[j][y2] == -1 {
            continue;
          }
          let mut val = grid[i][y1];
          if i != j || y1 != y2 {
            val += grid[j][y2];
          }
          let mut best = -100000;
          for di in 0..=1 {
            for dj in 0..=1 {
              let pi = i as isize - di;
              let pj = j as isize - dj;
              if pi >= 0 && pj >= 0 {
                best = best.max(dp[k - 1][pi as usize][pj as usize]);
              }
            }
          }
          if best > -100000 {
            dp[k][i][j] = best + val;
          }
        }
      }
    }
    0.max(dp[max_k][n - 1][n - 1])
  }
}

Complexity

• ⏰ Time complexity: O(n^3) — Three nested loops, each up to n.
• 🧺 Space complexity: O(n^3) — For the DP table.