LeetCode 1463: Cherry Pickup II Solution

Master LeetCode problem 1463 (Cherry Pickup II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1463. Cherry Pickup II

Hard

Array Dynamic Programming Matrix

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will iterate through each row from bottom to top and keep track of the maximum cherries collected at each cell for both robots. At each cell, we will consider all possible next cell choices for both robots and calculate the maximum cherries collected up to that cell. Finally, we will return the maximum cherries collected at the top row.

Initialize a 3D dp array to store the maximum cherries collected by both robots up to a particular cell.
Iterate through each row from bottom to top.
For each cell in the row, iterate through all possible next cell choices for both robots.
Calculate the maximum cherries collected for both robots at the current cell based on the cherries at the current cell and the maximum cherries collected from the next cell choices.
Update the dp array with the maximum cherries collected at each cell.
Return the maximum cherries collected at the top row.

Time Complexity: O(rows * cols^2) Space Complexity: O(rows * cols)

Solution Code

class Solution {
    public int cherryPickup(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int[][][] dp = new int[rows][cols][cols];
        
        for (int row = rows - 1; row >= 0; row--) {
            for (int col1 = 0; col1 < cols; col1++) {
                for (int col2 = 0; col2 < cols; col2++) {
                    int cherries = grid[row][col1] + (col1 != col2 ? grid[row][col2] : 0);
                    
                    for (int nextCol1 = col1 - 1; nextCol1 <= col1 + 1; nextCol1++) {
                        for (int nextCol2 = col2 - 1; nextCol2 <= col2 + 1; nextCol2++) {
                            if (nextCol1 >= 0 && nextCol1 < cols && nextCol2 >= 0 && nextCol2 < cols) {
                                dp[row][col1][col2] = Math.max(dp[row][col1][col2], cherries + dp[row + 1][nextCol1][nextCol2]);
                            }
                        }
                    }
                }
            }
        }
        
        return dp[0][0][cols - 1];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1463 (Cherry Pickup II)?

This page provides optimized solutions for LeetCode problem 1463 (Cherry Pickup II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1463 (Cherry Pickup II)?

The time complexity for LeetCode 1463 (Cherry Pickup II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1463 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1463 in Java, C++, or Python.

Back to LeetCode Solutions