Cherry pickup ii

Array Dynamic Programming Matrix

72.3% acceptance

Feb 25, 2026

4454

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
    let rows = grid.len();
    let cols = grid[0].len();
    let neg = i32::MIN / 2;
    // dp[c1][c2] = max cherries with robot1 at col c1, robot2 at col c2
    let mut dp = vec![vec![neg; cols]; cols];
    dp[0][cols - 1] = grid[0][0] + grid[0][cols - 1];

    for r in 1..rows {
      let mut ndp = vec![vec![neg; cols]; cols];
      for c1 in 0..cols {
        for c2 in 0..cols {
          if dp[c1][c2] == neg { continue; }
          for d1 in -1i32..=1 {
            let nc1 = c1 as i32 + d1;
            if nc1 < 0 || nc1 >= cols as i32 { continue; }
            let nc1 = nc1 as usize;
            for d2 in -1i32..=1 {
              let nc2 = c2 as i32 + d2;
              if nc2 < 0 || nc2 >= cols as i32 { continue; }
              let nc2 = nc2 as usize;
              let cherries = if nc1 == nc2 {
                grid[r][nc1]
              } else {
                grid[r][nc1] + grid[r][nc2]
              };
              let val = dp[c1][c2] + cherries;
              if val > ndp[nc1][nc2] {
                ndp[nc1][nc2] = val;
              }
            }
          }
        }
      }
      dp = ndp;
    }
    dp.iter().flatten().copied().max().unwrap_or(0)
  }
}