In this guide, you will get 1463. Cherry Pickup II LeetCode Solution with the best time and space complexity. The solution to Cherry Pickup II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
vector<vector<vector<int>>> mem(m,
vector<vector<int>>(n, vector<int>(n, -1)));
return cherryPickup(grid, 0, 0, n - 1, mem);
}
private:
// Returns the maximum cherries we can collect, where the robot #1 is on
// (x, y1) and the robot #2 is on (x, y2).
int cherryPickup(const vector<vector<int>>& grid, int x, int y1, int y2,
vector<vector<vector<int>>>& mem) {
if (x == grid.size())
return 0;
if (y1 < 0 || y1 == grid[0].size() || y2 < 0 || y2 == grid[0].size())
return 0;
if (mem[x][y1][y2] != -1)
return mem[x][y1][y2];
const int currRow = grid[x][y1] + (y1 == y2 ? 0 : 1) * grid[x][y2];
for (int d1 = -1; d1 <= 1; ++d1)
for (int d2 = -1; d2 <= 1; ++d2)
mem[x][y1][y2] =
max(mem[x][y1][y2],
currRow + cherryPickup(grid, x + 1, y1 + d1, y2 + d2, mem));
return mem[x][y1][y2];
}
}; /* code provided by PROGIEZ */
1463. Cherry Pickup II LeetCode Solution in Java
class Solution {
public int cherryPickup(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
int[][][] mem = new int[m][n][n];
Arrays.stream(mem).forEach(A -> Arrays.stream(A).forEach(B -> Arrays.fill(B, -1)));
return dp(grid, 0, 0, n - 1, mem);
}
// Returns the maximum cherries we can collect, where robot #1 is on (x, y1)
// and robot #2 is on (x, y2).
private int dp(int[][] grid, int x, int y1, int y2, int[][][] mem) {
if (x == grid.length)
return 0;
if (y1 < 0 || y1 == grid[0].length || y2 < 0 || y2 == grid[0].length)
return 0;
if (mem[x][y1][y2] != -1)
return mem[x][y1][y2];
final int currRow = grid[x][y1] + (y1 == y2 ? 0 : grid[x][y2]);
for (int d1 = -1; d1 <= 1; ++d1)
for (int d2 = -1; d2 <= 1; ++d2)
mem[x][y1][y2] = Math.max(mem[x][y1][y2], currRow + dp(grid, x + 1, y1 + d1, y2 + d2, mem));
return mem[x][y1][y2];
}
} // code provided by PROGIEZ
1463. Cherry Pickup II LeetCode Solution in Python
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
// dp[x][y1][y2] := the maximum cherries we can collect, where the robot #1
// is on (x, y1) and the robot #2 is on (x, y2)
vector<vector<vector<int>>> dp(m + 1,
vector<vector<int>>(n, vector<int>(n)));
for (int x = m - 1; x >= 0; --x)
for (int y1 = 0; y1 < n; ++y1)
for (int y2 = 0; y2 < n; ++y2) {
const int currRow = grid[x][y1] + (y1 != y2) * grid[x][y2];
for (int d1 = max(0, y1 - 1); d1 < min(n, y1 + 2); ++d1)
for (int d2 = max(0, y2 - 1); d2 < min(n, y2 + 2); ++d2)
dp[x][y1][y2] = max(dp[x][y1][y2], currRow + dp[x + 1][d1][d2]);
}
return dp[0][0][n - 1];
}
}; # code by PROGIEZ
