impl Solution {
pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut f = vec![vec![-1; n]; n];
let mut g = vec![vec![-1; n]; n];
f[0][n - 1] = grid[0][0] + grid[0][n - 1];
for i in 1..m {
for j1 in 0..n {
for j2 in 0..n {
let mut best = -1;
for dj1 in -1..=1 {
for dj2 in -1..=1 {
let dj1 = j1 as i32 + dj1;
let dj2 = j2 as i32 + dj2;
if dj1 >= 0 && dj1 < n as i32 && dj2 >= 0 && dj2 < n as i32 && f[dj1 as usize][dj2 as usize] != -1 {
best = best.max(f[dj1 as usize][dj2 as usize] + if j1 == j2 { grid[i][j1] } else { grid[i][j1] + grid[i][j2] });
}
}
}
g[j1][j2] = best;
}
}
std::mem::swap(&mut f, &mut g);
}
let mut ans = 0;
for j1 in 0..n {
ans = ans.max(*f[j1].iter().max().unwrap_or(&0));
}
ans
}
}
func cherryPickup(grid [][]int) int {
// f[i][j][k] 表示第i行摘取j,k桃子的最大值 // 令j<k
// f[i][j][k] = max(f[i-1][g(j,k)]) + grid[j] + grid[k]
n, m := len(grid), len(grid[0])
f := make([]int, m*m) // 当f[i][j] == 0 时表示该位置不可达
f[0*m+m-1] = grid[0][0]+grid[0][m-1] + 1 // +1是防止第一个元素为0，因为0表示不可达，最后结果-1即可
for i := 1; i < n; i++ {
p := make([]int, m*m)
for j := 0; j < min(i+1, m-1); j++ {
for z := max(m-1-i, j+1); z < m; z++ {
// 计算[j][z]的可考虑范围
for jj := max(0, j-1); jj <= min(m-1, j+1); jj++ {
for zz := max(jj+1, z-1); zz <= min(m-1, z+1); zz++ {
if f[jj*m+zz] == 0 { continue } // 这个位置不可达
p[j*m+z] = max(p[j*m+z], f[jj*m+zz]+grid[i][j]+grid[i][z])
}
}
}
}
f = p
}
_max := 0
for i := 0; i < m-1; i++ {
for j := i+1; j < m; j++ {
_max = max(f[i*m+j], _max)
}
}
return _max-1 // 减去添加的那个桃子
}
func max(a, b int) int { if a > b { return a }; return b }
func min(a, b int) int { if a < b { return a }; return b }
