1463. Cherry Pickup I I

# 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

## 题目大意 #

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

$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}$

其中：

$\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.$

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


Apr 8, 2023