Cherry Pickup II

This approach directly translates the problem's state transitions into a recursive function. The state is defined by the current row and the column positions of the two robots. Since both robots move down one row at a time, they are always in the same row.

• Define a recursive function solve(row, col1, col2) that returns the maximum cherries collected from the current row downwards, with robots at (row, col1) and (row, col2).
• Base Case: If row is the last row, return the cherries at the robots' positions. If col1 or col2 are out of bounds, return a very small number to signify an invalid path.
• Recursive Step: For the current state (row, col1, col2), calculate the cherries collected at this step. Then, explore all 9 possible next positions (col1 + d1, col2 + d2 where d1, d2 are in {-1, 0, 1}) in the next row by making recursive calls.
• The result for the current state is the sum of current cherries and the maximum value returned from the 9 recursive calls.
• The initial call is solve(0, 0, cols - 1).

We define a recursive function, say solve(row, col1, col2), which calculates the maximum cherries that can be collected from the current row to the bottom, given robot 1 is at (row, col1) and robot 2 is at (row, col2). The function works as follows:

• Base Case: When the robots reach the last row (row == rows - 1), they collect the cherries in their respective cells and the recursion stops. The value returned is grid[row][col1] + grid[row][col2] (or just grid[row][col1] if they are in the same cell).
• Recursive Step: For any other row, the function calculates the cherries collected at the current cells. Then, it explores all possible next moves for both robots. Robot 1 can move to col1-1, col1, or col1+1 in the next row, and similarly for robot 2. This gives 3 * 3 = 9 possible combinations of next positions. The function recursively calls itself for each of these 9 combinations and takes the maximum result. This maximum is added to the cherries collected at the current row.
• Boundary Checks: The function must handle cases where a robot moves outside the grid boundaries. Such paths are invalid and should return a value that ensures they are not chosen (e.g., a very small negative number).
• The initial call to the function is solve(0, 0, cols - 1).

class Solution {
    public int cherryPickup(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        return solve(0, 0, cols - 1, grid);
    }

    private int solve(int row, int col1, int col2, int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        // Boundary checks for columns
        if (col1 < 0 || col1 >= cols || col2 < 0 || col2 >= cols) {
            return Integer.MIN_VALUE;
        }

        // Cherries at the current step
        int cherries = grid[row][col1];
        if (col1 != col2) {
            cherries += grid[row][col2];
        }

        // Base case: last row
        if (row == rows - 1) {
            return cherries;
        }

        // Recursive step: explore all 9 possible next moves
        int maxFutureCherries = 0;
        for (int dc1 = -1; dc1 <= 1; dc1++) {
            for (int dc2 = -1; dc2 <= 1; dc2++) {
                maxFutureCherries = Math.max(maxFutureCherries, solve(row + 1, col1 + dc1, col2 + dc2, grid));
            }
        }

        return cherries + maxFutureCherries;
    }
}