One of the most exciting aspects of computer problems is how many various ways they can be solved. Based on several factors, one is superior to the other.
And sorting through all of them to find the finest one is a journey (though not one that will turn you into an alchemist), but one that will teach you a lot.
Today, we will discuss the cherry pickup problem. This problem will completely transform the way you think and widen your range of solutions.
Now that you know this problem's cool, let’s jump right into it.
Problem Statement
You are given an N X N matrix where each cell has either of three states.
0 = This block is free.
1 = This block contains a cherry.
-1 = This block contains nothing.
Maximize the number of cherries on the round trip from [0, 0] to [N - 1, N - 1] and then back to [0, 0].
Constraints
You can only take right and down steps while moving from [0, 0] to [N - 1, N - 1].
And while coming back from [N - 1, N - 1] to [0,0], you can only take left and up steps.
You can pass through the free block.
While passing through the cherry block, you can collect the cherry, but after this, it’s a free block.
You cannot pass through the block with thorns.
If you cannot complete the round trip, return -1.
Problem Explanation
This problem is about finding the maximum number of cherries you can collect in a round trip starting from the top-left corner of a square grid, moving down and right to reach the bottom-right corner, and then moving back up and left to reach the top-left corner again. The grid contains cells that are either empty, have cherries or have thorns. You cannot pass through cells with thorns. The task is to find the path that collects the maximum number of cherries.
Example 1
Let’s consider this 3 X 3 matrix.
As shown in the above image, we can pick a maximum of 3 cherries. Hence, the answer for the above matrix is 3.
Example 2
Consider the below image as matrix.
If we go from top-left to bottom-right and then back to top-left, taking the maximum cherry count path then,
Hence, choosing the maximum Cherry path will not always give maximum cherries in the round trip.
Approach Backtracking
We can solve this problem using Backtracking. Traverse every path from top-left to bottom-right, and for each path, find all paths back to top-right and find the maximum cherry paths. It’s like the cartesian product of all paths down to all paths up.
So we will have two functions( ‘traverseDown’) that will traverse from top-right to bottom-left and one ( ‘traverseUp’ ) that will traverse back from bottom-right to top-left.
Algorithm
Below is the algorithm in steps:
Define an N X N matrix, where each cell can contain a 0, 1, or -1.
Define a function to traverse all paths from top-left to bottom-right.
Define a function to traverse all paths from bottom-right to top-left.
In the traverseDown function, check if the block is valid. If it is not, return.
If we have reached the bottom-right block, call the traverseUp function.
In the traverseUp function, check if the block is valid. If it is not, return.
If we have reached the top-left block, update maxCherryCount if the current cherry count is greater than the previous maximum.
Store the number of cherries in the current block and collect them.
Traverse left and up in the traverseUp function.
Traverse right and down in the traverseDown function.
Backtrack by restoring the original number of cherries in the block.
Print the maximum number of cherries collected on the round trip from [0, 0] to [N - 1, N - 1] and back to [0, 0].
Implementation in C++
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
int maxCherryCount = 0;
// Function that will try all paths from bottom-right to top-left.
void traverseUp(int r, int c, int n, vector<vector<int>> &arr, int cherryCollected)
{
// Check if the block is valid.
if (r < 0 || c < 0 || r >= n || c >= n || arr[r][c] == -1)
{
return;
}
// If we are back to top-left, that means we have completed the traversal, so we update maxCherryCount.
if (r == 0 && c == 0)
{
maxCherryCount = max(maxCherryCount, cherryCollected);
}
// Store cherries in the block.
int cherries = arr[r][c];
// Now collect the cherry
arr[r][c] = 0;
// Traverse left and up.
traverseUp(r - 1, c, n, arr, cherryCollected + cherries);
traverseUp(r, c - 1, n, arr, cherryCollected + cherries);
// Backtrack.
arr[r][c] = cherries;
}
// Function to traverse all paths from top-left to bottom-right.
void traverseDown(int r, int c, int n, vector<vector<int>> &arr, int cherryCollected)
{
// Check if the block is valid.
if (r < 0 || c < 0 || r >= n || c >= n || arr[r][c] == -1)
{
return;
}
// Once we have reached the bottom-right now, traverse all paths back to the top-left.
if (r == n - 1 && c == n - 1)
{
traverseUp(r, c, n, arr, cherryCollected);
}
// Store cherries in the block.
int cherries = arr[r][c];
// Collect cherries.
arr[r][c] = 0;
// Traverse right and down.
traverseDown(r + 1, c, n, arr, cherryCollected + cherries);
traverseDown(r, c + 1, n, arr, cherryCollected + cherries);
// Backtrack.
arr[r][c] = cherries;
}
int main()
{
int n = 4;
vector<vector<int>> arr = {{0, 0, 1, 0},
{1, 0, 1, 0},
{-1, -1, 0, 1},
{1, -1, 0, 0}};
if (n == 1) {
cout << "Maximum cherries collected: " << arr[0][0] << endl;
return 0;
}
traverseDown(0, 0, n, arr, 0);
cout << "Maximum cherries collected: " << maxCherryCount << endl;
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
public class Solution {
private static int maxCherryCount;
// Function that will try all paths from bottom-right to top-left.
private static void traverseUp(int r, int c, int n, int[][] arr, int cherryCollected) {
// Check if the block is valid.
if (r < 0 || c < 0 || r >= n || c >= n || arr[r][c] == -1) {
return;
}
// If we are back to top-left, that means we have completed the traversal,
// so we update maxCherryCount.
if (r == 0 && c == 0) {
maxCherryCount = Math.max(maxCherryCount, cherryCollected);
return;
}
// Store cherries in the block.
int cherries = arr[r][c];
// Now collect the cherry
arr[r][c] = 0;
// Traverse left and up.
traverseUp(r - 1, c, n, arr, cherryCollected + cherries);
traverseUp(r, c - 1, n, arr, cherryCollected + cherries);
// Backtrack.
arr[r][c] = cherries;
}
// Function to traverse all paths from top-left to bottom-right.
private static void traverseDown(int r, int c, int n, int[][] arr, int cherryCollected) {
// Check if the block is valid.
if (r < 0 || c < 0 || r >= n || c >= n || arr[r][c] == -1) {
return;
}
// Once we have reached the bottom-right now, traverse all paths back to the top-left.
if (r == n - 1 && c == n - 1) {
traverseUp(r, c, n, arr, cherryCollected);
return;
}
// Store cherries in the block.
int cherries = arr[r][c];
// Collect cherries.
arr[r][c] = 0;
// Traverse right and down.
traverseDown(r + 1, c, n, arr, cherryCollected + cherries);
traverseDown(r, c + 1, n, arr, cherryCollected + cherries);
// Backtrack.
arr[r][c] = cherries;
}
public static void main(String[] args) {
int n = 4;
int[][] arr = {{0, 0, 1, 0}, {1, 0, 1, 0}, {-1, -1, 0, 1}, {1, -1, 0, 0}};
if (n == 1) {
System.out.println("Maximum cherries collected: " + arr[0][0]);
}
else{
traverseDown(0, 0, n, arr, 0);
System.out.println("Maximum cherries collected: " + maxCherryCount);
}
}
}
You can also try this code with Online Java Compiler
O( 2^(4N-4) ), where ‘N’ is the dimension of the matrix.
Reason: Total steps in a round trip = 4N-4, For moving from [0, 0] to [N - 1, N - 1] we take 2N - 2 steps ( Down steps = N - 1, Right steps = N - 1), so to complete a round trip double the steps of the one-way path.
For each step, we have two directions to choose from, and hence time complexity is 2 ^ (4N - 4).
Space Complexity
O(4N - 4), where ‘N’ is the dimension of the matrix.
Reason: Because of the stack space used in recursion, the maximum number of function calls in the stack is 4N - 4.
Let's see if we can apply Dynamic Programming to the above solution. One requirement for DP is that problems be solved using the solution to smaller subproblems (previously calculated), which is not the case here because we cannot divide the matrix into solved and unsolved sections where the solution to the unsolved part is somehow dependent on previously solved sections. As a result, we'll have to think up a new approach.
Approach DP
Let’s see how and why we can add DP to the above approach.This approach is more optimize than Backtracking.
So, instead of going from end to the beginning after reaching the end, we could reverse the approach and find two paths from beginning to the end. So, suppose we have two robots to perform our such task.
When we are at the start, robot 1 is at [r1,c1] and robot 2 is at [r2,c2]. We call four functions one for each case ( Right Right, Down Down, Right Down, Down Right ).
And we choose the case whose cherry count is maximum. So if we are in the same situation again, we can use the previously stored result to calculate the answer.
Since there are four variables, we’ll have to make a four-dimensional cache.
All we have to change in the above solution is to cache the result before returning and see if the result is calculated before, then return the result.
Another small improvement is that since both robots are starting from [0,0] and moving one step either right or down, r1+c1 = r2+c2 on every step.
So we can remove c2 from the function call, and it’s not variable now, so the cache dimension is reduced to three.
Algorithm
Define a class Solution with a public method cherryPickup that takes in a 2D vector grid as input and returns an integer.
Determine the length of the grid.
Create a 3D vector dp with dimensions len x len x len and initialize all values to INT_MIN (negative infinity).
Set the value of dp[len-1][len-1][len-1] to the value of grid[len-1][len-1] if it is not -1, otherwise set it to INT_MIN.
Loop through the 3D vector dp from the bottom right corner to the top left corner.
Calculate the second person's position based on the first person's position (i.e., m = i + j - k).
If either person lands on a negative value or a cell with -1 cherries, set the value in dp to negative infinity.
Calculate the number of cherries that the two people can pick up at the current positions (i.e., cherry = (i == k && j == m) ? grid[i][j] : grid[i][j] + grid[k][m]).
Calculate the maximum number of cherries that the two people can pick up at the current positions (i.e., max_cherry = max(max_cherry, dp[i+1][j][k+1]), etc.).
Update the value in dp for the current positions of the two people (i.e., dp[i][j][k] = cherry + max_cherry).
Return the maximum number of cherries that can be picked up starting from the top left corner (i.e., dp[0][0][0] if it is not INT_MIN, otherwise 0).
Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
// get length of the grid
int len = grid.size();
// create a 3D vector to store the dynamic programming results
vector<vector<vector<int>>> dp(len, vector<vector<int>>(len, vector<int>(len, INT_MIN)));
// set the value of the bottom right corner in the 3D vector based on the value of the corresponding cell in the input grid
dp[len-1][len-1][len-1] = grid[len-1][len-1] == -1 ? INT_MIN : grid[len-1][len-1];
// loop through the 3D vector from bottom right corner to top left corner
for (int i = len-1; i >= 0; i--) {
for (int j = len-1; j >= 0; j--) {
for (int k = len-1; k >= 0; k--) {
// calculate the position of the second person based on the position of the first person
int m = i + j - k;
// if either person lands on a negative value or a cell with -1 cherries, set the value in the 3D vector to negative infinity
if (m < 0 || m >= len || grid[i][j] == -1 || grid[k][m] == -1) {
dp[i][j][k] = INT_MIN;
continue;
}
// calculate the number of cherries that can be picked up by the two people at the current positions
int cherry = (i == k && j == m) ? grid[i][j] : grid[i][j] + grid[k][m];
// calculate the maximum number of cherries that can be picked up by the two people at the current positions
int max_cherry = INT_MIN;
if (i+1 < len && k+1 < len) max_cherry = max(max_cherry, dp[i+1][j][k+1]);
if (i+1 < len) max_cherry = max(max_cherry, dp[i+1][j][k]);
if (j+1 < len && k+1 < len) max_cherry = max(max_cherry, dp[i][j+1][k+1]);
if (j+1 < len) max_cherry = max(max_cherry, dp[i][j+1][k]);
// update the value in the 3D vector for the current positions of the two people
if (max_cherry != INT_MIN) {
dp[i][j][k] = cherry + max_cherry;
}
}
}
}
// return the maximum number of cherries that can be picked up starting from the top left corner
return dp[0][0][0] == INT_MIN ? 0 : dp[0][0][0];
}
};
int main() {
// define the input grid as a 2D vector
vector<vector<int>> grid = {
{0, 0, 1, 0},
{1, 0, 1, 0},
{-1, -1, 0, 1},
{1, -1, 0, 0}
};
// create a new instance of the Solution class and call cherryPickup()
Solution sol;
int result = sol.cherryPickup(grid);
cout << "Maximum cherries collected:" << result << endl;
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
class Solution {
public int cherryPickup(int[][] grid) {
// get length of the grid
int len = grid.length;
// create a 3D array to store the dynamic programming results
int[][][] dp = new int[len][len][len];
// fill the array with negative infinity values
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
Arrays.fill(dp[i][j], Integer.MIN_VALUE);
}
}
// set the value of the bottom right corner in the 3D array based on the value of the corresponding cell in the input grid
dp[len - 1][len - 1][len - 1] = grid[len - 1][len - 1] == -1 ? Integer.MIN_VALUE : grid[len - 1][len - 1];
// loop through the 3D array from bottom right corner to top left corner
for (int i = len - 1; i >= 0; i--) {
for (int j = len - 1; j >= 0; j--) {
for (int k = len - 1; k >= 0; k--) {
// calculate the position of the second person based on the position of the first person
int m = i + j - k;
// if either person lands on a negative value or a cell with -1 cherries, set the value in the 3D array to negative infinity
if (m < 0 || m >= len || grid[i][j] == -1 || grid[k][m] == -1) {
dp[i][j][k] = Integer.MIN_VALUE;
continue;
}
// calculate the number of cherries that can be picked up by the two people at the current positions
int cherry = (i == k && j == m) ? grid[i][j] : grid[i][j] + grid[k][m];
// calculate the maximum number of cherries that can be picked up by the two people at the current positions
int max = Integer.MIN_VALUE;
if (i + 1 < len && k + 1 < len) max = Math.max(max, dp[i + 1][j][k + 1]);
if (i + 1 < len) max = Math.max(max, dp[i + 1][j][k]);
if (j + 1 < len && k + 1 < len) max = Math.max(max, dp[i][j + 1][k + 1]);
if (j + 1 < len) max = Math.max(max, dp[i][j + 1][k]);
// update the value in the 3D array for the current positions of the two people
if (max != Integer.MIN_VALUE) {
dp[i][j][k] = cherry + max;
}
}
}
}
// return the maximum number of cherries that can be picked up starting from the top left corner
return dp[0][0][0] == Integer.MIN_VALUE ? 0 : dp[0][0][0];
}
}
class Main {
public static void main(String[] args) {
// define the input grid as a 2D array
int len = 4;
int[][] arr = {{0, 0, 1, 0}, {1, 0, 1, 0}, {-1, -1, 0, 1}, {1, -1, 0, 0}};
// create a new instance of the Solution class and call
Solution sol = new Solution();
int ans = sol.cherryPickup(arr);
System.out.println(ans);
}
}
You can also try this code with Online Java Compiler
Reason: Because the code uses a 3D dynamic programming array of size n^3 to store intermediate results, loops over each grid cell three times, resulting in three nested loops of size n each. The code performs a constant amount of work within each loop, so the overall time complexity is O(n^3).
Space Complexity
O( N^3 ), Where n is the length of one side of the input grid.
Reason: Because the code uses a 3D array dp of size n x n x n to store the dynamic programming results. Therefore, the space required to store dp is proportional to n^3. Additionally, the code uses some variables with constant space requirements, such as len and m, but these do not contribute significantly to the overall space complexity.
What is the Cherry Pickup problem in dynamic programming?
The Cherry Pickup problem is a dynamic programming problem where a robot must collect cherries from a grid with obstacles, where the robot starts at the top-left corner and must travel to the bottom-right corner. The robot can only move down or right, and can pick up cherries along the way. The problem requires finding the maximum number of cherries that the robot can collect.
How is the Cherry Pickup problem solved using backtracking?
In the Cherry Pickup problem, backtracking is used to explore all possible paths that the robot can take through the grid, while keeping track of the maximum number of cherries collected so far. The problem requires two recursive functions, one to traverse down from the top-left corner to the bottom-right corner, and another to traverse up from the bottom-right corner to the top-left corner.
Can dynamic programming and backtracking be used together?
Yes, dynamic programming and backtracking can be used together in some problems, where dynamic programming is used to store solutions to subproblems and backtracking is used to explore the space of possible solutions.
What is memoization in dynamic programming?
Memoization is a technique in dynamic programming that involves storing the results of expensive function calls and returning the cached result when the same inputs occur again, instead of repeating the calculation.
What is pruning in backtracking?
Pruning is a technique in backtracking that involves eliminating certain choices or branches of the search tree that are guaranteed not to lead to a valid solution, in order to reduce the search space and improve efficiency.
Conclusion
In this blog, we have discussed both the approaches. Solving questions like these teach you not only computer science concepts but also how to approach complex problems. We’ve got tons of such problems and blogs on the Coding Ninjas Platform.