LeetCode 741: Cherry Pickup Solution

Master LeetCode problem 741 (Cherry Pickup), 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.

741. Cherry Pickup

Hard

Array Dynamic Programming Matrix

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We will define a 4-dimensional dp array to store the maximum number of cherries that can be collected for each position of both players at each step. The state of the dp array will be defined as dp[r1][c1][r2][c2], where (r1, c1) represents the position of the first player and (r2, c2) represents the position of the second player.

At each step, both players can move either down or right, so there are 4 possible directions for the players' movements:

Player 1 moves down, player 2 moves down.
Player 1 moves down, player 2 moves right.
Player 1 moves right, player 2 moves down.
Player 1 moves right, player 2 moves right.

We will iterate through all possible directions and update the dp array accordingly. Finally, we return the maximum number of cherries that can be collected starting from (0, 0) to (n-1, n-1) and back to (0, 0).

Solution Code

class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][][][] dp = new int[n][n][n][n];

        for (int r1 = 0; r1 < n; r1++) {
            for (int c1 = 0; c1 < n; c1++) {
                for (int r2 = 0; r2 < n; r2++) {
                    int c2 = r1 + c1 - r2; // Calculate c2 based on r1, c1, and r2
                    if (c2 < 0 || c2 >= n) continue;
                    if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue;

                    int max = 0;
                    if (r1 > 0) max = Math.max(max, dp[r1 - 1][c1][r2][c2]);
                    if (c1 > 0) max = Math.max(max, dp[r1][c1 - 1][r2][c2]);
                    if (r2 > 0) max = Math.max(max, dp[r1][c1][r2 - 1][c2]);
                    if (c2 > 0) max = Math.max(max, dp[r1][c1][r2][c2 - 1]);

                    dp[r1][c1][r2][c2] = max + (r1 == r2 && c1 == c2 ? grid[r1][c1] : grid[r1][c1] + grid[r2][c2]);
                }
            }
        }

        return Math.max(0, dp[n - 1][n - 1][n - 1][n - 1]);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 741 (Cherry Pickup)?

This page provides optimized solutions for LeetCode problem 741 (Cherry Pickup) 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 741 (Cherry Pickup)?

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

Can I run code for LeetCode 741 on DevExCode?

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

Back to LeetCode Solutions