### Code

ì œì¶œ ë‚ ì§œ | ì‹œê°„ | ë©”ëª¨ë¦¬ |

2021/01/08 | 17 ms | 6.8 MB |

// 1463. Cherry Pickup II
//
// https://leetcode.com/problems/cherry-pickup-ii/
// There are two robots which are collecting cherries from the given grid.
// A robot is on the (0, 0), and another robot is on the (0, cols - 1).
// Robot can move toward the left bottom, toward bottom, right bottom.
// max function finds the maximum value among the inputs.
func max(input ...int) int {
val := -int(^uint(0)>>1) - 1
for _, i := range input {
if val < i {
val = i
}
}
return val
}
// cherryPickup function calculates the maximum cherries that can be collected.
// Let's define the coordinate of rows is x, the coordinate of cols is y.
// Pretend that the 3 Dimensional Slices DP[a][b][c] is the memoization of robot's move.
// Robot 1's coordinate is (a, b) and Robot 2's coordinate is (a, c).
// Then the DP[a][b][c] is the maximum value of collected cherries on that coordinates.
// All of the value in the DP are -1 when they are initialized.
// The spaces for the y have been created 2 tiles more than orignal because of robots move. Thus, the range of y is 1 to cols. (The range of x are as same as the original, so 0 to rows - 1.)
// The first rows of DP can be calculated with (0, 0) and (0, cols - 1). Thus the iterations for the x starts from 1 to rows - 1.
// Originally, y iterates 0 to cols - 1. However, y will be iterated by 1 to cols because tiles have been added.
// There are two ys for the robot1 and robot2. Thus, DP for the current position is DP[i][y1][y2] and it will be accumulated by previous one.
// Because DP solution is optimal, so the maximum value should be found before accumulated. To do this, there are 9 ways by considering the robots move.
// When it gets the maximum value of previous one, the number of cherry should be appened. But if y1 and y2 are the same position, only a sole value should be accumulated. Or, both value should be.
// The answer can be got on the last rows of DP, thus comparing each element should be done.
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+2)
for j := 0; j < cols+2; j++ {
dp[i][j] = make([]int, cols+2)
for k := 0; k < cols+2; k++ {
dp[i][j][k] = -1
}
}
}
dp[0][1][cols] = grid[0][0] + grid[0][cols-1]
answer := 0
for i := 1; i < rows; i++ {
for r1 := 1; r1 < cols+1; r1++ {
for r2 := 1; r2 < cols+1; r2++ {
dp[i][r1][r2] = max(
dp[i-1][r1-1][r2-1],
dp[i-1][r1-1][r2],
dp[i-1][r1-1][r2+1],
dp[i-1][r1][r2-1],
dp[i-1][r1][r2],
dp[i-1][r1][r2+1],
dp[i-1][r1+1][r2-1],
dp[i-1][r1+1][r2],
dp[i-1][r1+1][r2+1],
)
if dp[i][r1][r2] == -1 {
continue
} else {
if r1 == r2 {
dp[i][r1][r2] += grid[i][r1-1]
} else {
dp[i][r1][r2] += grid[i][r1-1] + grid[i][r2-1]
}
if i == rows-1 {
answer = max(answer, dp[i][r1][r2])
}
}
}
}
}
return answer
}

Go

ë³µì‚¬