Cherry Pickup II

Problem Statement

In this problem, you are given a matrix called grid which represents a cherry field. Each element in the grid indicates the number of cherries that can be collected from that specific cell. You have two robots to help you collect cherries:

• Robot #1 starts at the top-left corner of the matrix (0, 0).
• Robot #2 starts from the top-right corner (0, cols - 1) where cols is the number of columns in the matrix.

The objective is to calculate the maximum number of cherries both robots can collect by the time they reach the bottom row of the grid. Both robots can only move downwards to either the next left diagonal cell, the cell directly below, or the next right diagonal cell. Each time a robot visits a cell, all cherries in that cell are collected, and the cell becomes empty. If both robots land on the same cell, they still only collect the cherries once. They are not allowed to move outside the boundaries of the grid at any time.

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.

Constraints

• rows == grid.length
• cols == grid[i].length
• 2 <= rows, cols <= 70
• 0 <= grid[i][j] <= 100

Approach and Intuition

The above problem can be approached by considering how to maximize the collective harvesting as both robots progress through their paths from the top to the bottom of the grid. The two key dynamics here are optimizing the path for each robot such that they collect maximum cherries independently, and managing places where their paths overlap to ensure efficiency. Here's a breakdown of how the solution can be approached:

1. Dynamic Programming (DP):
   • A DP array can be used to store maximum cherries collected up to every possible position pair (i, j1, j2) of robot #1 and robot #2, where i is the row index, and j1 and j2 are the respective column indices for robots #1 and #2.
2. State Transition:
   • For every position (i, j1, j2) calculate and update the cherries collected by considering all moves from the previous row that could lead to this state which includes:
     • Moving from above left, above, or above right for both robots.
3. Managing Overlapping Positions:
   • Special attention is needed for the case where both robots end up on the same cell (i, j). Essentially, only one of the robots’ collections can count in such cases to avoid double counting.
4. Initialization and Boundary Conditions:
   • Start with the initial position where robot #1 is at (0, 0) and robot #2 is at (0, cols-1). As robots can only move within the boundary of the matrix, ensure the states respect these boundaries.
5. Result Computation:
   • After populating the DP matrix, the bottom row will display the maximum cherries collectible when both robots reach any of the columns in the last row. The maximum of these values will be the desired result.

Given the constraints of the grid size (up to 70x70), this dynamic programming approach should computationally feasible in terms of time complexity, even though it involves a three-dimensional DP array and multiple state transitions.

Solutions

class Solution {
    
    public int collectCherries(int[][] field) {
        int rows = field.length;
        int cols = field[0].length;
        int cache[][][] = new int[rows][cols][cols];
    
        for (int r = rows - 1; r >= 0; r--) {
            for (int c1 = 0; c1 < cols; c1++) {
                for (int c2 = 0; c2 < cols; c2++) {
                    int sum = 0;
                    // Collect cherries from current positions
                    sum += field[r][c1];
                    if (c1 != c2) {
                        sum += field[r][c2];
                    }
                    // Calculate maximum possible from next rows
                    if (r != rows - 1) {
                        int maxVal = 0;
                        for (int nextC1 = c1 - 1; nextC1 <= c1 + 1; nextC1++) {
                            for (int nextC2 = c2 - 1; nextC2 <= c2 + 1; nextC2++) {
                                if (nextC1 >= 0 && nextC1 < cols && nextC2 >= 0 && nextC2 < cols) {
                                    maxVal = Math.max(maxVal, cache[r + 1][nextC1][nextC2]);
                                }
                            }
                        }
                        sum += maxVal;
                    }
                    cache[r][c1][c2] = sum;
                }
            }
        }
        return cache[0][0][cols - 1];
    }
}