Find the maximum number of fruits collected

impl Solution {
  pub fn max_collected_fruits(fruits: Vec<Vec<i32>>) -> i32 {
    let n = fruits.len();
    
    // Child 1: starts (0,0), moves right/down/diagonal, always reaches (n-1,n-1).
    //   After step k (0-indexed), must have i+j = k (moving along anti-diagonals).
    //   Actually child 1 can move freely within the grid; path length = 2*(n-1) steps but problem says n-1 moves.
    //   Wait: the child makes exactly n-1 moves. Each move from (i,j) to one of {(i+1,j+1),(i+1,j),(i,j+1)}.
    //   Starting (0,0), after n-1 moves: i+j >= n-1 and i <= n-1, j <= n-1.
    //   To reach (n-1,n-1): need i=n-1,j=n-1, so i+j=2(n-1), but only n-1 moves - each increases i+j by at most 2.
    //   Max i+j increase = 2(n-1), so child 1 MUST always move diagonally: (i+1,j+1) each step.
    //   Path is exactly (0,0)->(1,1)->...->( n-1,n-1). Diagonal!
    
    // Child 2: starts (0,n-1), moves (i+1,j-1),(i+1,j),(i+1,j+1). Always increases row.
    //   n-1 moves, starts row 0, ends row n-1. Column: starts n-1, ends n-1.
    //   After n-1 steps, col changes by (moves right - moves left). Net col change = 0. Ends at (n-1, n-1). ✓
    
    // Child 3: starts (n-1,0), moves (i-1,j+1),(i,j+1),(i+1,j+1). Always increases col.
    //   n-1 moves, col starts 0 ends n-1. Row: starts n-1, ends n-1. Net row change = 0. Ends at (n-1,n-1). ✓
    
    // Child 1: fixed diagonal path. Collect all fruits[i][i].
    let child1: i32 = (0..n).map(|i| fruits[i][i]).sum();
    
    // Child 2 (row-by-row DP): at step i (row i), position (i, j2).
    // From (i,j2) can go to (i+1, j2-1), (i+1, j2), (i+1, j2+1).
    // Collect fruits[i][j2] if j2 != i (diagonal already taken by child 1).
    let mut dp2 = vec![i64::MIN; n];
    dp2[n-1] = fruits[0][n-1] as i64;
    for row in 1..n {
      let mut ndp = vec![i64::MIN; n];
      for j in 0..n {
        if dp2[j] == i64::MIN { continue; }
        for dj in -1i32..=1 {
          let nj = j as i32 + dj;
          if nj < 0 || nj >= n as i32 { continue; }
          let nj = nj as usize;
          // Collect fruits[row][nj], but if nj == row (diagonal), child1 already took it
          let gain = if nj == row { 0 } else { fruits[row][nj] as i64 };
          if ndp[nj] < dp2[j] + gain { ndp[nj] = dp2[j] + gain; }
        }
      }
      dp2 = ndp;
    }
    let best2 = dp2[n-1].max(0);
    
    // Child 3 (col-by-col DP): at step j (col j), position (i3, j).
    // From (i3, j) go to (i3-1, j+1), (i3, j+1), (i3+1, j+1).
    // Collect fruits[i3][j] if i3 != j (diagonal) and not already claimed by child2 at end.
    // Actually we need to track overlap between child2 and child3 too. This is complex.
    // But given the paths:
    // - Child 1: diagonal (k,k)
    // - Child 2: row k, some column j2
    // - Child 3: col k, some row i3
    // Overlap between 2 and 3 only at (n-1,n-1) which both paths end.
    // The grids are separate enough; children 2 and 3 can share cells only at (n-1,n-1).
    // DP for child3:
    let mut dp3 = vec![i64::MIN; n];
    dp3[n-1] = fruits[n-1][0] as i64;
    for col in 1..n {
      let mut ndp = vec![i64::MIN; n];
      for i in 0..n {
        if dp3[i] == i64::MIN { continue; }
        for di in -1i32..=1 {
          let ni = i as i32 + di;
          if ni < 0 || ni >= n as i32 { continue; }
          let ni = ni as usize;
          // Collect if not diagonal
          let gain = if ni == col { 0 } else { fruits[ni][col] as i64 };
          if ndp[ni] < dp3[i] + gain { ndp[ni] = dp3[i] + gain; }
        }
      }
      dp3 = ndp;
    }
    let best3 = dp3[n-1].max(0);
    
    (child1 as i64 + best2 + best3) as i32
  }
}