Problem

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

  • Robot #1 is located at the top-left corner (0, 0), and
  • Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below:

  • From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
  • When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
  • When both robots stay in the same cell, only one takes the cherries.
  • Both robots cannot move outside of the grid at any moment.
  • Both robots should reach the bottom row in grid.

Examples

Example 1

1
2
3
4
5
6

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2

1
2
3
4
5
6

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Solution

Method 1 – Dynamic Programming with Memoization

Intuition: We use 3D dynamic programming to track the maximum cherries both robots can collect as they move row by row. At each step, both robots have 3 possible moves, and we recursively try all combinations, caching results to avoid recomputation.

Approach:

  1. Define a DP function dp(r, c1, c2) where r is the current row, c1 and c2 are the columns of robot 1 and 2.
  2. If either robot moves out of bounds, return 0.
  3. Collect cherries at (r, c1) and (r, c2). If both robots are at the same cell, only count once.
  4. For the next row, try all 9 combinations of moves for both robots (-1, 0, 1 for each).
  5. Memoize results for each (r, c1, c2) to avoid recomputation.
  6. Start from row 0, columns 0 and cols-1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
  int cherryPickup(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<vector<int>>> memo(rows, vector<vector<int>>(cols, vector<int>(cols, -1)));
    function<int(int, int, int)> dp = [&](int r, int c1, int c2) {
      if (c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols) return 0;
      if (r == rows) return 0;
      if (memo[r][c1][c2] != -1) return memo[r][c1][c2];
      int ans = grid[r][c1];
      if (c1 != c2) ans += grid[r][c2];
      int mx = 0;
      for (int d1 = -1; d1 <= 1; ++d1) {
        for (int d2 = -1; d2 <= 1; ++d2) {
          mx = max(mx, dp(r+1, c1+d1, c2+d2));
        }
      }
      ans += mx;
      return memo[r][c1][c2] = ans;
    };
    return dp(0, 0, cols-1);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

func cherryPickup(grid [][]int) int {
  rows, cols := len(grid), len(grid[0])
  memo := make([][][]int, rows)
  for i := range memo {
    memo[i] = make([][]int, cols)
    for j := range memo[i] {
      memo[i][j] = make([]int, cols)
      for k := range memo[i][j] {
        memo[i][j][k] = -1
      }
    }
  }
  var dp func(r, c1, c2 int) int
  dp = func(r, c1, c2 int) int {
    if c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols {
      return 0
    }
    if r == rows {
      return 0
    }
    if memo[r][c1][c2] != -1 {
      return memo[r][c1][c2]
    }
    ans := grid[r][c1]
    if c1 != c2 {
      ans += grid[r][c2]
    }
    mx := 0
    for d1 := -1; d1 <= 1; d1++ {
      for d2 := -1; d2 <= 1; d2++ {
        v := dp(r+1, c1+d1, c2+d2)
        if v > mx {
          mx = v
        }
      }
    }
    ans += mx
    memo[r][c1][c2] = ans
    return ans
  }
  return dp(0, 0, cols-1)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
  public int cherryPickup(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Integer[][][] memo = new Integer[rows][cols][cols];
    return dp(0, 0, cols - 1, grid, memo);
  }
  private int dp(int r, int c1, int c2, int[][] grid, Integer[][][] memo) {
    int rows = grid.length, cols = grid[0].length;
    if (c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols) return 0;
    if (r == rows) return 0;
    if (memo[r][c1][c2] != null) return memo[r][c1][c2];
    int ans = grid[r][c1];
    if (c1 != c2) ans += grid[r][c2];
    int mx = 0;
    for (int d1 = -1; d1 <= 1; d1++) {
      for (int d2 = -1; d2 <= 1; d2++) {
        mx = Math.max(mx, dp(r + 1, c1 + d1, c2 + d2, grid, memo));
      }
    }
    ans += mx;
    memo[r][c1][c2] = ans;
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
  fun cherryPickup(grid: Array<IntArray>): Int {
    val rows = grid.size
    val cols = grid[0].size
    val memo = Array(rows) { Array(cols) { IntArray(cols) { -1 } } }
    fun dp(r: Int, c1: Int, c2: Int): Int {
      if (c1 !in 0 until cols || c2 !in 0 until cols) return 0
      if (r == rows) return 0
      if (memo[r][c1][c2] != -1) return memo[r][c1][c2]
      var ans = grid[r][c1]
      if (c1 != c2) ans += grid[r][c2]
      var mx = 0
      for (d1 in -1..1) {
        for (d2 in -1..1) {
          mx = maxOf(mx, dp(r + 1, c1 + d1, c2 + d2))
        }
      }
      ans += mx
      memo[r][c1][c2] = ans
      return ans
    }
    return dp(0, 0, cols - 1)
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
  def cherryPickup(self, grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    memo: dict[tuple[int, int, int], int] = {}
    def dp(r: int, c1: int, c2: int) -> int:
      if c1 < 0 or c1 >= cols or c2 < 0 or c2 >= cols:
        return 0
      if r == rows:
        return 0
      key = (r, c1, c2)
      if key in memo:
        return memo[key]
      ans = grid[r][c1]
      if c1 != c2:
        ans += grid[r][c2]
      mx = 0
      for d1 in (-1, 0, 1):
        for d2 in (-1, 0, 1):
          mx = max(mx, dp(r+1, c1+d1, c2+d2))
      ans += mx
      memo[key] = ans
      return ans
    return dp(0, 0, cols-1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

impl Solution {
  pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
    let rows = grid.len();
    let cols = grid[0].len();
    let mut memo = vec![vec![vec![-1; cols]; cols]; rows];
    fn dp(r: usize, c1: i32, c2: i32, grid: &Vec<Vec<i32>>, memo: &mut Vec<Vec<Vec<i32>>>) -> i32 {
      let rows = grid.len();
      let cols = grid[0].len() as i32;
      if c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols {
        return 0;
      }
      if r == rows {
        return 0;
      }
      let (c1u, c2u) = (c1 as usize, c2 as usize);
      if memo[r][c1u][c2u] != -1 {
        return memo[r][c1u][c2u];
      }
      let mut ans = grid[r][c1u];
      if c1 != c2 {
        ans += grid[r][c2u];
      }
      let mut mx = 0;
      for d1 in -1..=1 {
        for d2 in -1..=1 {
          let v = dp(r+1, c1+d1, c2+d2, grid, memo);
          if v > mx {
            mx = v;
          }
        }
      }
      ans += mx;
      memo[r][c1u][c2u] = ans;
      ans
    }
    dp(0, 0, (cols-1) as i32, &grid, &mut memo)
  }
}

Complexity

  • ⏰ Time complexity: O(rows * cols * cols * 9) = O(rows * cols^2)
  • 🧺 Space complexity: OO(rows * cols^2) for memoization

Method 2 – Bottom-Up Dynamic Programming (Tabulation)

Intuition

Instead of solving subproblems recursively, we build the solution from the bottom row up. For each row and every possible pair of robot positions, we compute the maximum cherries that can be collected, using previously computed results for the next row. This avoids recursion and stack overhead.

Approach

  1. Let dp[r][c1][c2] represent the maximum cherries collected starting from row r with robots at columns c1 and c2.
  2. Initialize the base case for the last row: for every pair (c1, c2), sum the cherries at those positions (count once if same cell).
  3. Iterate from the second-last row up to the first row.
  4. For each possible pair of columns (c1, c2) for the two robots, try all 9 combinations of moves for the next row (-1, 0, 1 for each robot).
  5. For each move, add the cherries at (r, c1) and (r, c2) (count once if same cell), plus the best result from the next row.
  6. The answer is dp[0][0][cols-1].
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
  int cherryPickup(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<vector<int>>> dp(rows, vector<vector<int>>(cols, vector<int>(cols, 0)));
    for (int c1 = 0; c1 < cols; ++c1) {
      for (int c2 = 0; c2 < cols; ++c2) {
        dp[rows-1][c1][c2] = (c1 == c2) ? grid[rows-1][c1] : grid[rows-1][c1] + grid[rows-1][c2];
      }
    }
    for (int r = rows-2; r >= 0; --r) {
      for (int c1 = 0; c1 < cols; ++c1) {
        for (int c2 = 0; c2 < cols; ++c2) {
          int ans = 0;
          for (int d1 = -1; d1 <= 1; ++d1) {
            for (int d2 = -1; d2 <= 1; ++d2) {
              int nc1 = c1 + d1, nc2 = c2 + d2;
              if (nc1 >= 0 && nc1 < cols && nc2 >= 0 && nc2 < cols) {
                ans = max(ans, dp[r+1][nc1][nc2]);
              }
            }
          }
          dp[r][c1][c2] = (c1 == c2 ? grid[r][c1] : grid[r][c1] + grid[r][c2]) + ans;
        }
      }
    }
    return dp[0][0][cols-1];
  }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

func cherryPickup(grid [][]int) int {
  rows, cols := len(grid), len(grid[0])
  dp := make([][][]int, rows)
  for i := range dp {
    dp[i] = make([][]int, cols)
    for j := range dp[i] {
      dp[i][j] = make([]int, cols)
    }
  }
  for c1 := 0; c1 < cols; c1++ {
    for c2 := 0; c2 < cols; c2++ {
      if c1 == c2 {
        dp[rows-1][c1][c2] = grid[rows-1][c1]
      } else {
        dp[rows-1][c1][c2] = grid[rows-1][c1] + grid[rows-1][c2]
      }
    }
  }
  for r := rows-2; r >= 0; r-- {
    for c1 := 0; c1 < cols; c1++ {
      for c2 := 0; c2 < cols; c2++ {
        ans := 0
        for d1 := -1; d1 <= 1; d1++ {
          for d2 := -1; d2 <= 1; d2++ {
            nc1, nc2 := c1+d1, c2+d2
            if nc1 >= 0 && nc1 < cols && nc2 >= 0 && nc2 < cols {
              if dp[r+1][nc1][nc2] > ans {
                ans = dp[r+1][nc1][nc2]
              }
            }
          }
        }
        if c1 == c2 {
          dp[r][c1][c2] = grid[r][c1] + ans
        } else {
          dp[r][c1][c2] = grid[r][c1] + grid[r][c2] + ans
        }
      }
    }
  }
  return dp[0][0][cols-1]
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
  public int cherryPickup(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int[][][] dp = new int[rows][cols][cols];
    for (int c1 = 0; c1 < cols; c1++) {
      for (int c2 = 0; c2 < cols; c2++) {
        dp[rows-1][c1][c2] = (c1 == c2) ? grid[rows-1][c1] : grid[rows-1][c1] + grid[rows-1][c2];
      }
    }
    for (int r = rows-2; r >= 0; r--) {
      for (int c1 = 0; c1 < cols; c1++) {
        for (int c2 = 0; c2 < cols; c2++) {
          int ans = 0;
          for (int d1 = -1; d1 <= 1; d1++) {
            for (int d2 = -1; d2 <= 1; d2++) {
              int nc1 = c1 + d1, nc2 = c2 + d2;
              if (nc1 >= 0 && nc1 < cols && nc2 >= 0 && nc2 < cols) {
                ans = Math.max(ans, dp[r+1][nc1][nc2]);
              }
            }
          }
          dp[r][c1][c2] = (c1 == c2 ? grid[r][c1] : grid[r][c1] + grid[r][c2]) + ans;
        }
      }
    }
    return dp[0][0][cols-1];
  }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
  fun cherryPickup(grid: Array<IntArray>): Int {
    val rows = grid.size
    val cols = grid[0].size
    val dp = Array(rows) { Array(cols) { IntArray(cols) } }
    for (c1 in 0 until cols) {
      for (c2 in 0 until cols) {
        dp[rows-1][c1][c2] = if (c1 == c2) grid[rows-1][c1] else grid[rows-1][c1] + grid[rows-1][c2]
      }
    }
    for (r in rows-2 downTo 0) {
      for (c1 in 0 until cols) {
        for (c2 in 0 until cols) {
          var ans = 0
          for (d1 in -1..1) {
            for (d2 in -1..1) {
              val nc1 = c1 + d1
              val nc2 = c2 + d2
              if (nc1 in 0 until cols && nc2 in 0 until cols) {
                ans = maxOf(ans, dp[r+1][nc1][nc2])
              }
            }
          }
          dp[r][c1][c2] = (if (c1 == c2) grid[r][c1] else grid[r][c1] + grid[r][c2]) + ans
        }
      }
    }
    return dp[0][0][cols-1]
  }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
  def cherryPickup(self, grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp: list[list[list[int]]] = [[[0]*cols for _ in range(cols)] for _ in range(rows)]
    for c1 in range(cols):
      for c2 in range(cols):
        dp[rows-1][c1][c2] = grid[rows-1][c1] if c1 == c2 else grid[rows-1][c1] + grid[rows-1][c2]
    for r in range(rows-2, -1, -1):
      for c1 in range(cols):
        for c2 in range(cols):
          ans = 0
          for d1 in (-1, 0, 1):
            for d2 in (-1, 0, 1):
              nc1, nc2 = c1 + d1, c2 + d2
              if 0 <= nc1 < cols and 0 <= nc2 < cols:
                ans = max(ans, dp[r+1][nc1][nc2])
          dp[r][c1][c2] = (grid[r][c1] if c1 == c2 else grid[r][c1] + grid[r][c2]) + ans
    return dp[0][0][cols-1]
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
  pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
    let rows = grid.len();
    let cols = grid[0].len();
    let mut dp = vec![vec![vec![0; cols]; cols]; rows];
    for c1 in 0..cols {
      for c2 in 0..cols {
        dp[rows-1][c1][c2] = if c1 == c2 { grid[rows-1][c1] } else { grid[rows-1][c1] + grid[rows-1][c2] };
      }
    }
    for r in (0..rows-1).rev() {
      for c1 in 0..cols {
        for c2 in 0..cols {
          let mut ans = 0;
          for d1 in -1..=1 {
            for d2 in -1..=1 {
              let nc1 = c1 as i32 + d1;
              let nc2 = c2 as i32 + d2;
              if nc1 >= 0 && nc1 < cols as i32 && nc2 >= 0 && nc2 < cols as i32 {
                ans = ans.max(dp[r+1][nc1 as usize][nc2 as usize]);
              }
            }
          }
          dp[r][c1][c2] = if c1 == c2 { grid[r][c1] } else { grid[r][c1] + grid[r][c2] } + ans;
        }
      }
    }
    dp[0][0][cols-1]
  }
}

Complexity

  • ⏰ Time complexity: O(rows * cols^2 * 9) = O(rows * cols^2)
  • 🧺 Space complexity: O(rows * cols^2)