首次看题目时，发现是困难。立马想到了，动态规划。

再看题目， 摘樱桃，还要返回摘两次，求摘最多的樱桃。

大脑第一反应就是：

先使用动态规划，找到 0 0 到 n-1 n-1处走过的最大樱桃， 并记录路径path。

然后根据路径path，将摘过的樱桃置为0，表示已经被摘过了。 然后再次摘樱桃。

两次摘过的樱桃之和就是目标的结果。

嗯，应该是，那就开写。

func cherryPickup(grid [][]int) int {
    ans := 0

    n := len(grid)
    dp := make([][]int, 0)
    for i := 0; i < n; i++ {
        dp = append(dp, make([]int, n))
    }

    // 1 表示上一个路径是 上
    // 2 表示上一个路径是 左
    path := make([][]int, 0)
    for i := 0; i < n; i++ {
        path = append(path, make([]int, n))
    }

    // 记录首次dp的轨迹，开始第一次摘
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if i == 0 && j == 0 {
                dp[0][0] = grid[0][0]
                continue
            }
            if grid[i][j] == -1 {
                dp[i][j] = -1
                continue
            }

            if (i - 1 < 0 || grid[i-1][j] == -1 || dp[i-1][j] == -1) && (j - 1 < 0 || grid[i][j-1] == -1 || dp[i][j-1] == -1) {
                dp[i][j] = -1
                continue
            }

            if i - 1 < 0 || grid[i-1][j] == -1 || dp[i-1][j] == -1 {
                dp[i][j] = dp[i][j-1] + grid[i][j]
                path[i][j] = 2
                continue
            }
            if j - 1 < 0 || grid[i][j-1] == -1 || dp[i][j-1] == -1 {
                dp[i][j] = dp[i-1][j] + grid[i][j]
                path[i][j] = 1
                continue
            }
           
            if dp[i][j-1] > dp[i-1][j] {
                path[i][j] = 2
                dp[i][j] = dp[i][j-1] + grid[i][j]
            } else {
                path[i][j] = 1
                dp[i][j] = dp[i-1][j] + grid[i][j]
            }
        }
    }

    ans += dp[n-1][n-1]
    if ans == -1 {
        return 0
    }
    // 回溯路径， 清理已经被摘过的樱桃
    ii, jj := n-1, n-1
    for path[ii][jj] != 0 {
        grid[ii][jj] = 0
        if path[ii][jj] == 1 {
            ii--
        } else {
            jj--
        }
    }
    // 第二次摘樱桃
    grid[0][0] = 0
    dp = make([][]int, 0)
    for i := 0; i < n; i++ {
        dp = append(dp, make([]int, n))
    }
     for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if i == 0 && j == 0 {
                dp[0][0] = grid[0][0]
                continue
            }
            if grid[i][j] == -1 {
                dp[i][j] = -1
                continue
            }

            if (i - 1 < 0 || grid[i-1][j] == -1 || dp[i-1][j] == -1) && (j - 1 < 0 || grid[i][j-1] == -1 || dp[i][j-1] == -1) {
                dp[i][j] = -1
                continue
            }

            if i - 1 < 0 || grid[i-1][j] == -1 || dp[i-1][j] == -1 {
                dp[i][j] = dp[i][j-1] + grid[i][j]
                path[i][j] = 2
                continue
            }
            if j - 1 < 0 || grid[i][j-1] == -1 || dp[i][j-1] == -1 {
                dp[i][j] = dp[i-1][j] + grid[i][j]
                path[i][j] = 1
                continue
            }
           
            if dp[i][j-1] > dp[i-1][j] {
                path[i][j] = 2
                dp[i][j] = dp[i][j-1] + grid[i][j]
            } else {
                path[i][j] = 1
                dp[i][j] = dp[i-1][j] + grid[i][j]
            }
        }
    }
    // 将两次摘的樱桃数相加
    return ans + dp[n-1][n-1]
}

最后发现通过 53/59 , 差一点点点点。 其实差很多。

通过研究这个未通过的案例， 发现我虽然2次摘樱桃都是最大值， 但并不能证明最终采摘的樱桃数是最大的。

最后瞄了一眼答案， 来回摘2次樱桃数最多，又不能重复摘， 那找两个人同时摘不就好了吗。 

附上leetcode标准答案

func cherryPickup(grid [][]int) int {
    n := len(grid)
    f := make([][][]int, n*2-1)
    for i := range f {
        f[i] = make([][]int, n)
        for j := range f[i] {
            f[i][j] = make([]int, n)
            for k := range f[i][j] {
                f[i][j][k] = math.MinInt32
            }
        }
    }
    f[0][0][0] = grid[0][0]
    for k := 1; k < n*2-1; k++ {
        for x1 := max(k-n+1, 0); x1 <= min(k, n-1); x1++ {
            y1 := k - x1
            if grid[x1][y1] == -1 {
                continue
            }
            for x2 := x1; x2 <= min(k, n-1); x2++ {
                y2 := k - x2
                if grid[x2][y2] == -1 {
                    continue
                }
                res := f[k-1][x1][x2] // 都往右
                if x1 > 0 {
                    res = max(res, f[k-1][x1-1][x2]) // 往下，往右
                }
                if x2 > 0 {
                    res = max(res, f[k-1][x1][x2-1]) // 往右，往下
                }
                if x1 > 0 && x2 > 0 {
                    res = max(res, f[k-1][x1-1][x2-1]) // 都往下
                }
                res += grid[x1][y1]
                if x2 != x1 { // 避免重复摘同一个樱桃
                    res += grid[x2][y2]
                }
                f[k][x1][x2] = res
            }
        }
    }
    return max(f[n*2-2][n-1][n-1], 0)
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/cherry-pickup/solutions/1656418/zhai-ying-tao-by-leetcode-solution-1h3k/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。