Problem Statement
Given a n x m 2d integer array called matrix where matrix[i][j] represents the number of cherries you can pick up from the (i, j) cell. Given two robots that can collect cherries, one is located at the top-leftmost (0, 0) cell and the other at the top-rightmost (0, m-1) cell.
Return the maximum number of cherries that can be picked by the two robots in total, following these rules:
- Robots that are standing on
(i, j)cell can only move to cell(i + 1, j - 1),(i + 1, j), or(i + 1, j + 1), if it exists in the matrix. - A robot will pick up all the cherries in a given cell when it passes through that cell.
- If both robots come to the same cell at the same time, only one robot takes the cherries.
- Both robots must reach the bottom row in matrix.
Examples
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.
Different Approach
1️⃣ Recursive Approach
Why Greedy Approach will not work:
As we have to return the maximum cherries collected, the first approach that comes to our mind is to take a greedy approach and always form a path by locally choosing the option that gives us more cherries. But there is no ‘uniformity’ in the values of the matrix. Therefore, it can happen that whenever we make a local choice that gives us a better path, we actually take a path that, in later stages, yields fewer cherries.
As a greedy solution doesn’t work, our next choice will be to try out all the possible paths. To generate all possible paths we will use recursion.
In this question, there are fixed starting points but variable ending points, but as per the movements of robots, we know that they will end in the last row. They have to move together at a time to the next row because if we separately find the maximum cherries picked up by each robot, it can happen that the same cell cherries gets counted twice for each of the robots.
Steps to form the recursive solution:
- Express the problem in terms of indexes: This question is slightly different from all the previous questions, here we are given two starting points from where the two robots can move. We are given an
‘N*M’matrix. Therefore, four parametersi1, j1, i2, and j2needs to be defined, to describe the positions of both of the robots. Each pair(i, j) wil describe the present cell of each of the robots.
If we observe, initially the two robots are at the first row, and they always move to the row below them every time, so they will always be in the same row. Therefore two different variables i1 and i2, to describe their positions are redundant. We can just use single parameter i, which tells us in which row of the grid both of them are.
Hence the function can be modified to take 3 parameters only. 'i', 'j1' and 'j2'. f(i, j1, j2) will give the maximum number of cherries collected by 1st robot from cell[i, j1] till last row and 2nd robot from cell[i, j2] till last row combined.
- Try out all possible choices at a given index: At every cell, there are 3 choices for each robot, to the bottom cell, to the bottom-right cell or to the bottom-left cell. Now, we need to understand that both of the robots needs to move together. Both of them can individually take three moves but say one of them moves to bottom-left, then the other one can have three different choices for each move taken by the first robot.
Hence there are total of 9 different options at every f(i, j1, j2) to move both the robots together. Now we can manually write these 9 options or we can observe a pattern in them, first one of the robots moves to one side and the other one takes tries all three choices, then again the first robot moves, then the second one, and so on. This pattern can be easily captured by using two nested loops that change the column numbers(j1 and j2).
- Base Case:
- Note: If (j1===j2), as discussed in the base case, only consider cherries collected by one of them otherwise consider cherries collected by both of them.
/*It is pseudocode and it is not tied to
any specific programming language*/
f(i,j1, j2){
// Base case
for(di = -1; di <= 1; di++){
for(dj = -1; dj <=1; dj++){
ans = 0;
if(j1 == j2){
ans = mat[i][j1] + f(i + 1, j1 + di, j2 + dj)
else
ans = mat[i][j1] + mat[i][j2] + f(i + 1, j1 + di, j2 + dj)
}
}
}
}- Take the maximum of all choices: As we need to find the maximum cherries picked, return the maximum of the choices.
/*It is pseudocode and it is not tied to
any specific programming language*/
f(i,j1, j2){
//Base case
maxi = INT_MIN
for(di = -1; di <= 1; di++){
for(dj = -1; dj <=1; dj++){
ans = 0;
if(j1 == j2)
ans = mat[i][j1] + f(i + 1, j1 + di, j2 + dj)
else
ans = mat[i][j1] + mat[i][j2] + f(i + 1, j1 + di, j2 + dj)
maxi = max(maxi, ans)
}
}
return maxi
}- Base cases:
- When i == N-1, it means we are at the last row, so we need to return from here. Now it can happen that in the last row, both the robots are at the same cell, in this condition return cherries collected by one of them only, mat[i][j1], otherwise return sum of cherries collected by both, mat[i][j1] + mat[i][j1][j2].
At every cell, there are 3 choices individually, to the bottom cell, to the bottom-right cell or to the bottom-left cell. As the robots are moving to the bottom row, at max they will reach the last row, from where they return, so they will never go out of the bounding index.
To move to the bottom-right cell or to the bottom-left cell, it can happen that robots may go out of bound. So we need to handle that case, return -1e9, whenever robots go out of bound, in this way this path will not be selected by the calling function as we have to return the maximum cherries.
/*It is pseudocode and it is not tied to
any specific programming language*/
f(i,j1, j2){
if(j1 < 0 || j1>= m || j2 < 0 || j2 >= m) return -1e9
if(i == n-1) {
if(j1 == j2)
return mat[i][j1]
else
return mat[i][j1] + mat[i][j2]
}
}Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Recursive function to calculate the maximum cherries that can be collected
by two robots starting from the current row.
@param row - Current row index
@param col1 - Column index of the first robot
@param col2 - Column index of the second robot
@param rows - Total number of rows in the grid
@param cols - Total number of columns in the grid
@param grid - The 2D grid of cherries
@return Maximum cherries that can be collected starting from the current position
*/
int collectCherries(int row, int col1, int col2, int rows, int cols, vector<vector<int>> &grid) {
// Base case: If any robot moves out of bounds
if (col1 < 0 || col1 >= cols || col2 < 0 || col2 >= cols) {
return INT_MIN; // Return a very small value to indicate invalid move
}
// Base case: If we are on the last row
if (row == rows - 1) {
// If both robots are at the same position, count cherries only once
if (col1 == col2)
return grid[row][col1];
else
return grid[row][col1] + grid[row][col2];
}
// Variable to store the maximum cherries collected
int maxCherries = INT_MIN;
// Explore all possible moves for both robots (-1, 0, +1 in the next row)
for (int move1 = -1; move1 <= 1; move1++) {
for (int move2 = -1; move2 <= 1; move2++) {
int currentCherries;
// If both robots are at the same position, count cherries only once
if (col1 == col2) {
currentCherries = grid[row][col1] + collectCherries(row + 1, col1 + move1, col2 + move2, rows, cols, grid);
} else {
// If robots are at different positions, count cherries from both cells
currentCherries = grid[row][col1] + grid[row][col2] + collectCherries(row + 1, col1 + move1, col2 + move2, rows, cols, grid);
}
// Update the maximum cherries collected
maxCherries = max(maxCherries, currentCherries);
}
}
return maxCherries; // Return the maximum cherries collected
}
public:
/*
Function to calculate the maximum cherries that can be collected by two robots
starting from the first row, one at the leftmost column and the other at the rightmost column.
@param grid - The 2D grid of cherries
@return Maximum cherries that can be collected
*/
int cherryPickup(vector<vector<int>> &grid) {
int rows = grid.size(); // Total number of rows in the grid
int cols = grid[0].size(); // Total number of columns in the grid
// Start the recursive calculation from row 0 with robots at columns 0 and cols - 1
return collectCherries(0, 0, cols - 1, rows, cols, grid);
}
};
int main() {
// Define the grid of cherries
vector<vector<int>> grid{
{2, 3, 1, 2},
{3, 4, 2, 2},
{5, 6, 3, 5},
};
// Create an instance of the Solution class
Solution solution;
// Calculate and print the maximum cherries that can be collected
cout << solution.cherryPickup(grid) << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(3^(N)*3^(N)), whereNis the number of row. As, for each cell, each of the robots has 3 options and there are N rows to be considered. - Space Complexity:
O(N), at maximum the depth of the recursive stack can go up to N.
2️⃣ Memoization
If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.
In order to convert a recursive solution to memoization the following steps will be taken:
- Declare a dp array of size [n][m][m]: As there are three changing parameters(i, j1 and j2) in the recursive solution, and the maximum value they can attain is (n-1) for 'i' as it detones the row and (m-1) for both 'j1' and 'j2' as it denotes the column. So we will require a dp matrix of n*m*m.
- The dp array stores the calculations of subproblems, dp[i][j1][j2] represents the maximum number of cherries collected by 1st robot from cell[i, j1] till last row and 2nd robot from cell[i, j2] till last row combined. Initially, fill the array with -1, to indicate that no subproblem has been solved yet.
- While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
- Store the value of subproblem: Whenever, a subproblem is encountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Recursive function to calculate the maximum cherries that can be collected
by two robots starting from the current row with memoization.
@param row - Current row index
@param col1 - Column index of the first robot
@param col2 - Column index of the second robot
@param rows - Total number of rows in the grid
@param cols - Total number of columns in the grid
@param grid - The 2D grid of cherries
@param dp - 3D DP table to store results of previously computed states
@return Maximum cherries that can be collected starting from the current position
*/
int collectCherries(int row, int col1, int col2, int rows, int cols, vector<vector<int>> &grid, vector<vector<vector<int>>> &dp) {
// Base case: If any robot moves out of bounds
if (col1 < 0 || col1 >= cols || col2 < 0 || col2 >= cols) {
return INT_MIN; // Return a very small value to indicate invalid move
}
// Base case: If we are on the last row
if (row == rows - 1) {
if (col1 == col2)
return grid[row][col1];
else
return grid[row][col1] + grid[row][col2];
}
// Check if the result is already computed
if (dp[row][col1][col2] != -1) {
return dp[row][col1][col2];
}
// Variable to store the maximum cherries collected
int maxCherries = INT_MIN;
// Explore all possible moves for both robots (-1, 0, +1 in the next row)
for (int move1 = -1; move1 <= 1; move1++) {
for (int move2 = -1; move2 <= 1; move2++) {
int currentCherries;
// If both robots are at the same position, count cherries only once
if (col1 == col2) {
currentCherries = grid[row][col1] + collectCherries(row + 1, col1 + move1, col2 + move2, rows, cols, grid, dp);
} else {
// If robots are at different positions, count cherries from both cells
currentCherries = grid[row][col1] + grid[row][col2] + collectCherries(row + 1, col1 + move1, col2 + move2, rows, cols, grid, dp);
}
// Update the maximum cherries collected
maxCherries = max(maxCherries, currentCherries);
}
}
// Store the result in the DP table and return it
return dp[row][col1][col2] = maxCherries;
}
public:
/*
Function to calculate the maximum cherries that can be collected by two robots
starting from the first row, one at the leftmost column and the other at the rightmost column.
@param grid - The 2D grid of cherries
@return Maximum cherries that can be collected
*/
int cherryPickup(vector<vector<int>> &grid) {
int rows = grid.size(); // Total number of rows in the grid
int cols = grid[0].size(); // Total number of columns in the grid
// 3D DP table initialized to -1
vector<vector<vector<int>>> dp(rows, vector<vector<int>>(cols, vector<int>(cols, -1)));
// Start the recursive calculation from row 0 with robots at columns 0 and cols - 1
return collectCherries(0, 0, cols - 1, rows, cols, grid, dp);
}
};
int main() {
// Define the grid of cherries
vector<vector<int>> grid{
{2, 3, 1, 2},
{3, 4, 2, 2},
{5, 6, 3, 5},
};
// Create an instance of the Solution class
Solution solution;
// Calculate and print the maximum cherries that can be collected
cout << solution.cherryPickup(grid) << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N*M*M) * 9. At max, there will be N*M*M calls of recursion to solve a new problem and in every call, two nested loops together run for 9 times. - Space Complexity:
O(N) + O(N*M*M). We are using a recursion stack space of O(N), where N is the path length and an external DP Array of size ‘N*M*M’.
3️⃣ Tabulation
In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:
- Declare a dp array of size [n][m][m]: As there are three changing parameters(i, j1 and j2) in the recursive solution, and the maximum value they can attain is (n-1) for 'i' as it detones the row and (m-1) for both 'j1' and 'j2' as it denotes the column. So we will require a dp matrix of n*m*m.
- The dp array stores the calculations of subproblems, dp[i][j1][j2] represents the maximum number of cherries collected by 1st robot from cell[i, j1] till last row and 2nd robot from cell[i, j2] till last row combined. Initially, fill the array with -1, to indicate that no subproblem has been solved yet.
- Setting Base Cases in the Array: In the recursive code, our base condition was when we reach the last row, therefore in our dp array, we will also initialize dp[n-1][][], i.e (the last plane of 3D Array) as the base condition. Dp[n-1][j1][j2] means the first robot is at (n-1,j1) and the second robot is at (n-1,j2). As this is the last row, its value will be equal to mat[i][j1], if (j1==j2) and mat[i][j1] + mat[i][j2] otherwise.
- Iterative Computation Using Loops: As the last row of the dp is already filled for base condition, now start moving from dp[n-2][][] to dp[0][][]. First set three nested loops to do this traversal.
- Inside the three nested loops( say i, j1, j2 as loop variables), use the recursive relations, i.e again set two nested loops to try all the nine options. The outer three loops are just for traversal, and the inner two loops that run for 9 times mainly decide, what should be the value of the cell.
- Inside the inner two nested loops, calculate an answer as we had done in the recursive relation, but this time using values from the next plane of the 3D DP Array( dp[i+1][x][y] instead of recursive calls, where x and y will vary according to inner 2 nested loops).
- Choosing the maximum: As the question asks for maximum cherries that can be collected so, set dp[i][j1][j2] as the maximum of all the 9 options possible.
- Returning the answer: The element dp[0][0][m-1] of the dp array is returned because it holds the optimal solution to the entire problem after the computation has been completed.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution{
private:
/* Function to find the maximum cherries
that can be collected using tabulation */
int func(int n, int m, vector<vector<int>> &matrix) {
// Initialize a 3D DP array to store computed results
vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(m, 0)));
// Initialize the DP array for the last row
for (int j1 = 0; j1 < m; j1++) {
for (int j2 = 0; j2 < m; j2++) {
if (j1 == j2)
dp[n - 1][j1][j2] = matrix[n - 1][j1];
else
dp[n - 1][j1][j2] = matrix[n - 1][j1] + matrix[n - 1][j2];
}
}
/* Outer nested loops for traversing the DP array
from the second-to-last row up to the first row*/
for (int i = n - 2; i >= 0; i--) {
for (int j1 = 0; j1 < m; j1++) {
for (int j2 = 0; j2 < m; j2++) {
int maxi = INT_MIN;
// Inner nested loops to try out 9 options
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
int ans;
if (j1 == j2)
ans = matrix[i][j1];
else
ans = matrix[i][j1] + matrix[i][j2];
// Check if the move is valid
if ((j1 + di < 0 || j1 + di >= m) || (j2 + dj < 0 || j2 + dj >= m))
/* A very large negative value
to represent an invalid move*/
ans += -1e9;
else
ans += dp[i + 1][j1 + di][j2 + dj];
// Update the maximum result
maxi = max(ans, maxi);
}
}
/* Store the maximum result for
this state in the DP array*/
dp[i][j1][j2] = maxi;
}
}
}
/* The maximum cherries that can be collected
is stored at the top-left corner of the DP array*/
return dp[0][0][m - 1];
}
public:
//Function to find the maximum cherries picked
int cherryPickup(vector<vector<int>> &matrix){
int n = matrix.size();
int m = matrix[0].size();
//Return the answer
return func(n, m, matrix);
}
};
int main() {
vector<vector<int>> matrix{
{2, 3, 1, 2},
{3, 4, 2, 2},
{5, 6, 3, 5},
};
//Create an instance of Solution class
Solution sol;
// Call the maximumChocolates function and print the result
cout << sol.cherryPickup(matrix);
return 0;
}
Complexity Analysis:
- Time Complexity:
O((N*M*M)*9), The outer nested loops run for (N*M*M) times and the inner two nested loops run for 9 times - Space Complexity:
O(N*M*M), As an external array of size ‘N*M*M’ is used.
4️⃣ Space Optimization
If we observe, we find that to compute dp[i][j1][j2], the value which is needed is from dp[i+1][][] only. Therefore it is not necessary to store a three-dimensional array. Instead, a two-dimensional array can do the same work and we can just update it upon moving from one plane to the other in the 3D Array.
The Steps to space optimize the tabulation approach are as follows:
- Initially, take a dummy 2D Array ( say front), initialize this array in the same way it was done in the Tabulation Approach also initialize a 2D Array( say cur), which will be needed in the traversal.
- Now set three nested loops to traverse the 3D Array, from the second last plane. Following the same approach as tabulation, find the maximum number of cherries collected at each cell. To calculate it we have all the values in our ‘front’ 2D Array.
- Previously, the value of dp[i][j1][j2] was assigned to maxi, now simply assign cur[j1][j2] to maxi. Then whenever the plane of the 3D DP(the first parameter) is going to change, assign the front to cur.
- At last, return front[0][m-1] as our answer as it will store the cumulative answer of maximum cherries.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution{
private:
/* Function to find the maximum cherries
that can be collected usnig space optimization*/
int func(int n, int m, vector<vector<int>> &matrix){
/* Declare two 2D vectors 'front'
and 'cur' to store computed results*/
vector<vector<int>> front(m, vector<int>(m, 0));
vector<vector<int>> cur(m, vector<int>(m, 0));
// Initialize 'front' for the last row
for (int j1 = 0; j1 < m; j1++) {
for (int j2 = 0; j2 < m; j2++) {
if (j1 == j2)
front[j1][j2] = matrix[n - 1][j1];
else
front[j1][j2] = matrix[n - 1][j1] + matrix[n - 1][j2];
}
}
/* Outer nested loops for traversing the DP array
from the second-to-last row up to the first row*/
for (int i = n - 2; i >= 0; i--) {
for (int j1 = 0; j1 < m; j1++) {
for (int j2 = 0; j2 < m; j2++) {
int maxi = INT_MIN;
// Inner nested loops to try out 9 options
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
int ans;
if (j1 == j2)
ans = matrix[i][j1];
else
ans = matrix[i][j1] + matrix[i][j2];
// Check if the move is valid
if ((j1 + di < 0 || j1 + di >= m) || (j2 + dj < 0 || j2 + dj >= m))
/* A very large negative value
to represent an invalid move*/
ans += -1e9;
else
ans += front[j1 + di][j2 + dj];
// Update the maximum result
maxi = max(ans, maxi);
}
}
/* Store the maximum result for
this state in the 'cur' array*/
cur[j1][j2] = maxi;
}
}
/* Update 'front' with the values
from 'cur' for the next iteration*/
front = cur;
}
/* The maximum cherries that can be collected
is stored at the top-left corner of the 'front'*/
return front[0][m - 1];
}
public:
//Function to find the maximum cherries collected
int cherryPickup(vector<vector<int>> &matrix){
int n = matrix.size();
int m = matrix[0].size();
//Return the answer
return func(n, m, matrix);
}
};
int main() {
vector<vector<int>> matrix{
{2, 3, 1, 2},
{3, 4, 2, 2},
{5, 6, 3, 5},
};
//Create an instance of Solution class
Solution sol;
// Call the maximumChocolates function and print the result
cout << sol.cherryPickup(matrix);
return 0;
}
Complexity Analysis:
- Time Complexity:
O((N*M*M)*9), The outer nested loops run for (N*M*M) times and the inner two nested loops run for 9 times. - Space Complexity:
O(M*M). As an external array of size ‘M*M’ is used.