We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cherry Pickup

Difficulty: Hard

Problem Description

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers. You need to return the maximum number of cherries you can collect by starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down, then returning to (0, 0) by moving left or up. Cells can contain cherries (1), be empty (0), or be blocked by thorns (-1).

Key Insights

  • The path to collect cherries can be divided into two parts: going to the bottom-right corner and returning to the top-left corner.
  • Cherries are collected when moving through cells with value 1, and these cells become empty after being passed.
  • You can only move either right or down on the way to (n - 1, n - 1) and left or up on the return trip.
  • The problem can be approached using dynamic programming to keep track of the maximum cherries collected at each step.

Space and Time Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Solution

To tackle this problem, we can use a dynamic programming approach where we maintain a 3D DP array. The state dp[r1][c1][c2] represents the maximum cherries collected when reaching cell (r1, c1) with the second person reaching (r2, c2) where r2 + c2 = r1 + c1. We check all possible previous positions to update the current state. The key is to handle the cases where both paths hit a thorn.

Code Solutions

def cherryPickup(grid):
    n = len(grid)
    if grid[0][0] == -1 or grid[n - 1][n - 1] == -1:
        return 0

    dp = [[[-1] * n for _ in range(n)] for _ in range(n)]
    dp[0][0][0] = grid[0][0]

    for r1 in range(n):
        for c1 in range(n):
            for c2 in range(n):
                r2 = r1 + c1 - c2
                if r2 < 0 or r2 >= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:
                    continue
                cherries = grid[r1][c1] + (grid[r2][c2] if c1 != c2 else 0)
                max_cherries = 0
                for dr1, dc1 in [(0, 1), (1, 0)]:
                    for dr2, dc2 in [(0, 1), (1, 0)]:
                        prev_r1, prev_c1 = r1 - dr1, c1 - dc1
                        prev_r2, prev_c2 = r2 - dr2, c2 - dc2
                        if 0 <= prev_r1 < n and 0 <= prev_c1 < n and 0 <= prev_r2 < n and 0 <= prev_c2 < n:
                            max_cherries = max(max_cherries, dp[prev_r1][prev_c1][prev_c2])
                dp[r1][c1][c2] = max_cherries + cherries

    result = max(0, dp[n - 1][n - 1][n - 1])
    return result
← Back to All Questions