Problem Statement
You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.
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).
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 passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
- When both robots stay in the same cell, only one takes the cherries.
- Both robots cannot move outside of the grid at any moment.
- Both robots should reach the bottom row in
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.
Try here before watching the video.
Video Solution
Java Code
class Solution {
int[] dir = new int[]{-1, 0, 1};
private int solve(int row, int col1, int col2, int rows, int cols, int[][] grid, int[][][] dp) {
if(row == rows) {
return 0;
}
if(col1 < 0 || col2 < 0 || col1 >= cols || col2 >= cols) {
return Integer.MIN_VALUE;
}
if(dp[row][col1][col2] != -1) {
return dp[row][col1][col2];
}
int maxCherries = 0;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
maxCherries = Math.max(maxCherries, solve(row + 1, col1 + dir[i], col2 + dir[j], rows, cols, grid, dp));
}
}
if(col1 == col2) {
maxCherries += grid[row][col1];
} else {
maxCherries += (grid[row][col1] + grid[row][col2]);
}
return dp[row][col1][col2] = maxCherries;
}
public int cherryPickup(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int[][][] dp = new int[rows][cols][cols];
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
Arrays.fill(dp[i][j], -1);
}
}
return solve(0, 0, cols - 1, rows, cols, grid, dp);
}
}
C++ Code
class Solution {
public:
int dir[3] = {-1, 0, 1};
int solve(int row, int col1, int col2, int rows, int cols, vector<vector<int>>& grid, vector<vector<vector<int>>>& dp) {
if (row == rows) {
return 0;
}
if (col1 < 0 || col2 < 0 || col1 >= cols || col2 >= cols) {
return INT_MIN;
}
if (dp[row][col1][col2] != -1) {
return dp[row][col1][col2];
}
int maxCherries = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
maxCherries = max(maxCherries, solve(row + 1, col1 + dir[i], col2 + dir[j], rows, cols, grid, dp));
}
}
if (col1 == col2) {
maxCherries += grid[row][col1];
} else {
maxCherries += (grid[row][col1] + grid[row][col2]);
}
return dp[row][col1][col2] = maxCherries;
}
int cherryPickup(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
vector<vector<vector<int>>> dp(rows, vector<vector<int>>(cols, vector<int>(cols, -1)));
return solve(0, 0, cols - 1, rows, cols, grid, dp);
}
};
Python Code
class Solution:
dir = [-1, 0, 1]
def solve(self, row, col1, col2, rows, cols, grid, dp):
if row == rows:
return 0
if col1 < 0 or col2 < 0 or col1 >= cols or col2 >= cols:
return float('-inf')
if dp[row][col1][col2] != -1:
return dp[row][col1][col2]
maxCherries = 0
for i in range(3):
for j in range(3):
maxCherries = max(maxCherries, self.solve(row + 1, col1 + self.dir[i], col2 + self.dir[j], rows, cols, grid, dp))
if col1 == col2:
maxCherries += grid[row][col1]
else:
maxCherries += grid[row][col1] + grid[row][col2]
dp[row][col1][col2] = maxCherries
return maxCherries
def cherryPickup(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
dp = [[[-1] * cols for _ in range(cols)] for _ in range(rows)]
return self.solve(0, 0, cols - 1, rows, cols, grid, dp)
Javascript Code
var cherryPickup = function(grid) {
const dir = [-1, 0, 1];
const rows = grid.length;
const cols = grid[0].length;
const dp = new Array(rows).fill(0).map(() => new Array(cols).fill(0).map(() => new Array(cols).fill(-1)));
const solve = (row, col1, col2) => {
if (row === rows) {
return 0;
}
if (col1 < 0 || col2 < 0 || col1 >= cols || col2 >= cols) {
return Number.MIN_SAFE_INTEGER;
}
if (dp[row][col1][col2] !== -1) {
return dp[row][col1][col2];
}
let maxCherries = 0;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
maxCherries = Math.max(maxCherries, solve(row + 1, col1 + dir[i], col2 + dir[j]));
}
}
if (col1 === col2) {
maxCherries += grid[row][col1];
} else {
maxCherries += grid[row][col1] + grid[row][col2];
}
dp[row][col1][col2] = maxCherries;
return maxCherries;
};
return solve(0, 0, cols - 1);
};
Go Code
func cherryPickup(grid [][]int) int {
rows := len(grid)
cols := len(grid[0])
dp := make([][][]int, rows)
for i := range dp {
dp[i] = make([][]int, cols)
for j := range dp[i] {
dp[i][j] = make([]int, cols)
for k := range dp[i][j] {
dp[i][j][k] = -1
}
}
}
return solve(0, 0, cols-1, rows, cols, grid, dp)
}
func solve(row, col1, col2, rows, cols int, grid [][]int, dp [][][]int) int {
if row == rows {
return 0
}
if col1 < 0 || col2 < 0 || col1 >= cols || col2 >= cols {
return math.MinInt32
}
if dp[row][col1][col2] != -1 {
return dp[row][col1][col2]
}
maxCherries := 0
for i := -1; i <= 1; i++ {
for j := -1; j <= 1; j++ {
maxCherries = max(maxCherries, solve(row+1, col1+i, col2+j, rows, cols, grid, dp))
}
}
if col1 == col2 {
maxCherries += grid[row][col1]
} else {
maxCherries += grid[row][col1] + grid[row][col2]
}
dp[row][col1][col2] = maxCherries
return maxCherries
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Complexity Analysis
Time Complexity: O(M * N2)
Space Complexity: O(M * N2)