1463. Cherry Pickup II #

Problem #

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

Problem Summary #

Given a rows x cols matrix grid representing a field of cherries. The number in each cell of grid represents the number of cherries you can collect. You have two robots to help you collect cherries: Robot 1 starts from the top-left cell (0,0), and Robot 2 starts from the top-right cell (0, cols-1). Following the rules below, return the maximum number of cherries the two robots can collect:

From cell (i,j), a robot can move to cell (i+1, j-1), (i+1, j), or (i+1, j+1).
When a robot passes through a cell, it picks up all the cherries in that cell, and then this position becomes an empty cell, i.e. a cell with no cherries.
When two robots arrive at the same cell at the same time, only one of them can pick up the cherries.
The two robots cannot move outside grid at any moment.
Both robots must eventually reach the bottom row of grid.

Solution Thought Process #

If you have no idea, you can first try a brute-force DFS solution. After reading the problem, you can analyze that finding the maximum number of cherries contains many overlapping subproblems, so the natural idea is to use dynamic programming. Judging from the data scale, a scale of 100 can at most guarantee that an algorithm with O(n^3) time complexity will not time out.
This problem has 2 variables: one is the row number, and the other is the column where a robot is located. More specifically, each move of a robot can only go downward, not upward, so the row numbers of the 2 robots must be the same. The column numbers of the two robots are different. In summary, there are 3 variables: 1 row number and 2 column numbers. Define dp[i][j][k] to represent the maximum number of cherries that can be collected when the first robot goes from (0,0) to coordinate (i,k), and the second robot goes from (0,n-1) to coordinate (i,k). The state transition equation is:
\[ 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} \]
where:
\[ \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. \]
That is, during the state transition process, you need to enumerate j1 in [j1 - 1, j1, j1 + 1]; similarly, enumerate j2 in [j2 - 1, j2, j2 + 1]. Each state transition needs to enumerate these 3*3 = 9 states.
The boundary condition is dp[i][0][n-1] = grid[0][0] + grid[0][n-1]. The final answer is stored in row dp[m-1]; loop to find the maximum value among dp[m-1][j1][j2], and the problem is solved.

Code #

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