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) 坐标，两者最多能收集樱桃的数目。状态转移方程为：

{{< katex display >}} dp[i][j][k] = max \begin{pmatrix}\begin{array}{lr} dp[i-1][f(j_1))][f(j_2)] + grid[i][j_1] + grid[i][j_2], j_1\neq j_2 \ dp[i-1][f(j_1))][f(j_2)] + grid[i][j_1], j_1 = j_2 \end{array} \end{pmatrix} {{< /katex>}}

其中：

{{< katex display >}} \left{\begin{matrix}f(j_1) \in [0,n), f(j_1) - j_1 \in [-1,0,1]\ f(j_2) \in [0,n), f(j_2) - j_2 \in [-1,0,1]\end{matrix}\right. {{< /katex>}}

即状态转移过程中需要在 [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]
}

Uh oh!