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 II

Difficulty: Hard

Problem Description

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell. You have two robots that can collect cherries for you: Robot #1 is located at the top-left corner (0, 0), and Robot #2 is located at the top-right corner (0, cols - 1). Return the maximum number of cherries collection using both robots by following the rules about their movement and collection.

Key Insights

  • The robots can move to adjacent cells in the next row, which creates a dynamic programming problem.
  • Both robots collect cherries from their respective cells, but if they land on the same cell, only one can collect cherries.
  • The solution requires tracking the maximum cherries collected as the robots move down the grid.
  • The state can be represented by the row index and the column indices of both robots.

Space and Time Complexity

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

Solution

The problem can be solved using dynamic programming. We use a 3D DP table where dp[row][col1][col2] represents the maximum cherries collected when Robot #1 is at column col1 and Robot #2 is at column col2 in row row. The value is calculated based on the possible previous positions of both robots from the previous row. The solution iteratively builds up from the top of the grid to the bottom, checking all valid movements.

Code Solutions

def cherryPickup(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[-1] * cols for _ in range(cols)]
    
    # Initialize the first row
    for j1 in range(cols):
        for j2 in range(cols):
            if j1 + j2 < cols:  # Both robots must be within bounds
                dp[j1][j2] = grid[0][j1] + (grid[0][j2] if j1 != j2 else 0)
                
    # Iterate over each row
    for i in range(1, rows):
        new_dp = [[-1] * cols for _ in range(cols)]
        for j1 in range(cols):
            for j2 in range(cols):
                if dp[j1][j2] == -1: continue
                for nj1 in (j1-1, j1, j1+1):
                    for nj2 in (j2-1, j2, j2+1):
                        if 0 <= nj1 < cols and 0 <= nj2 < cols:
                            cherries = grid[i][nj1]
                            if nj1 != nj2:
                                cherries += grid[i][nj2]
                            new_dp[nj1][nj2] = max(new_dp[nj1][nj2], dp[j1][j2] + cherries)
        dp = new_dp
    
    return max(dp[j1][j2] for j1 in range(cols) for j2 in range(cols) if dp[j1][j2] != -1)
← Back to All Questions