Cherry pickup

/*
 * 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.
 * 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
 */
impl Solution {
  pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
    let n = grid.len();
    const NEG: i32 = i32::MIN / 2;
    let mut dp = vec![vec![NEG; n]; n];
    dp[0][0] = grid[0][0];

    for t in 1..2 * n - 1 {
      let mut ndp = vec![vec![NEG; n]; n];
      let r_lo = t.saturating_sub(n - 1);
      let r_hi = n.min(t + 1);
      for r1 in r_lo..r_hi {
        let c1 = t - r1;
        if grid[r1][c1] == -1 { continue; }
        for r2 in r1..r_hi {
          let c2 = t - r2;
          if c2 >= n { continue; }
          if grid[r2][c2] == -1 { continue; }
          let mut best = NEG;
          // person 1 previous row: r1 or r1-1; person 2: r2 or r2-1
          for &pr1 in &[r1, r1.wrapping_sub(1)] {
            if pr1 >= n { continue; }
            for &pr2 in &[r2, r2.wrapping_sub(1)] {
              if pr2 >= n { continue; }
              let (lo, hi) = (pr1.min(pr2), pr1.max(pr2));
              if dp[lo][hi] != NEG {
                best = best.max(dp[lo][hi]);
              }
            }
          }
          if best == NEG { continue; }
          let cherries = if r1 == r2 { grid[r1][c1] } else { grid[r1][c1] + grid[r2][c2] };
          ndp[r1][r2] = ndp[r1][r2].max(best + cherries);
        }
      }
      dp = ndp;
    }
    0.max(dp[n - 1][n - 1])
  }
}