1463. Cherry Pickup II

题目

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots  by following the rules below:

• From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
• When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
• When both robots stay on the same cell, only one of them takes the cherries.
• Both robots cannot move outside of the grid at any moment.
• Both robots should reach the bottom row in the grid.

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

Input: 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]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Example 3:

Input: grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
Output: 22

Example 4:

Input: grid = [[1,1],[1,1]]
Output: 4

Constraints:

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

题目大意

给你一个 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 最底下一行。

解题思路

• 如果没有思路可以先用暴力解法 DFS 尝试。读完题可以分析出求最多樱桃数目，里面包含了很多重叠子问题，于是乎自然而然思路是用动态规划。数据规模上看，100 的数据规模最多能保证 O(n^3) 时间复杂度的算法不超时。
• 这一题的变量有 2 个，一个是行号，另外一个是机器人所在的列。具体来说，机器人每走一步的移动范围只能往下走，不能往上走，所以 2 个机器人所在行号一定相同。两个机器人的列号不同。综上，变量有 3 个，1 个行号和2 个列号。定义 dp[i][j][k] 代表第一个机器人从 (0,0) 走到 (i,k) 坐标，第二个机器人从 (0,n-1) 走到 (i,k) 坐标，两者最多能收集樱桃的数目。状态转移方程为 ：

其中：

即状态转移过程中需要在 `[j1 - 1, j1, j1 + 1]` 中枚举 `j1`，同理，在 在 `[j2 - 1, j2, j2 + 1]` 中枚举 `j2`，每个状态转移需要枚举这 3*3 = 9 种状态。

• 边界条件 dp[i][0][n-1] = grid[0][0] + grid[0][n-1]，最终答案存储在 dp[m-1] 行中，循环找出 dp[m-1][j1][j2] 中的最大值，到此该题得解。

代码

package leetcode

func cherryPickup(grid [][]int) int {
	rows, cols := len(grid), len(grid[0])
	dp := make([][][]int, rows)
	for i := 0; i < rows; i++ {
		dp[i] = make([][]int, cols)
		for j := 0; j < cols; j++ {
			dp[i][j] = make([]int, cols)
		}
	}
	for i := 0; i < rows; i++ {
		for j := 0; j <= i && j < cols; j++ {
			for k := cols - 1; k >= cols-1-i && k >= 0; k-- {
				max := 0
				for a := j - 1; a <= j+1; a++ {
					for b := k - 1; b <= k+1; b++ {
						sum := isInBoard(dp, i-1, a, b)
						if a == b && i > 0 && a >= 0 && a < cols {
							sum -= grid[i-1][a]
						}
						if sum > max {
							max = sum
						}
					}
				}
				if j == k {
					max += grid[i][j]
				} else {
					max += grid[i][j] + grid[i][k]
				}
				dp[i][j][k] = max
			}
		}
	}
	count := 0
	for j := 0; j < cols && j < rows; j++ {
		for k := cols - 1; k >= 0 && k >= cols-rows; k-- {
			if dp[rows-1][j][k] > count {
				count = dp[rows-1][j][k]
			}
		}
	}
	return count
}

func isInBoard(dp [][][]int, i, j, k int) int {
	if i < 0 || j < 0 || j >= len(dp[0]) || k < 0 || k >= len(dp[0]) {
		return 0
	}
	return dp[i][j][k]
}

---