摘樱桃 II

题目描述：

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
两个机器人在任意时刻都不能移动到 grid 外面。
两个机器人最后都要到达 grid 最底下一行。

示例 1：

输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出：24
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
樱桃总数为： 12 + 12 = 24 。
示例 2：

输入：grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出：28
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
樱桃总数为： 17 + 11 = 28 。
示例 3：

输入：grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
输出：22
示例 4：

输入：grid = [[1,1],[1,1]]
输出：4

提示：

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

思路:

时间复杂度：O(n^3),空间复杂度O(n^2)

三维dp，滚动更新，压缩成二维
dp(i, j1, j2)表示在第i层的时候第一个机器人在j1，第二个机器人在j2，所能摘到的最多的樱桃

代码:

func cherryPickup(grid [][]int) int {
    m,n := len(grid), len(grid[0])
    dp := make([][]int, n)
    for i:=0;i<n;i++{
        dp[i] = make([]int, n)
        for j:=0;j<n;j++{
            dp[i][j] = -1
        }
    }
    dp[0][n-1] = grid[0][0] + grid[0][n-1]
     nxt := make([][]int, n)
    for i := range nxt {
        nxt[i] = make([]int, n)
    }

    nxt[0][n - 1] = grid[0][0] + grid[0][n - 1]
    
    for i:=1;i<m;i++{
        for j1:=0;j1<n;j1++{
            for j2:=0;j2<n;j2++{
                best := -1
               
                for j:=j1-1;j<=j1+1;j++{
                    for k:=j2-1;k<=j2+1;k++{
                        if j<0 || j >=n || k<0 || k >=n || dp[j][k] == -1{
                            continue
                        }
                        tmp := dp[j][k]
                        if j1 == j2{
                            tmp += grid[i][j1]
                        }else{
                            tmp += grid[i][j1]+grid[i][j2]
                        }
                        best = max(best,tmp)
                    }
                }
                nxt[j1][j2] = best
            }
        }
        
        dp, nxt = nxt, dp
    }

    ans := 0
    for j1 := 0; j1 < n; j1 ++ {
        for j2 := 0; j2 < n; j2 ++ {
            ans = max(ans, dp[j1][j2])
        }
    }

    return ans

}

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

代码效率：

执行用时：24 ms, 在所有 Go 提交中击败了88.89%的用户
内存消耗：3.7 MB, 在所有 Go 提交中击败了88.89%的用户