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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Cherry Pickup II

Number: 1559

Difficulty: Hard

Paid? No

Companies: Flipkart, Google, Meta, Amazon

Problem Description

Given a grid representing a field of cherries, two robots start at the top corners (left for Robot #1 and right for Robot #2) and move down row by row. Both robots can move to three possible cells in the next row (down-left, down, down-right). When a robot visits a cell, it collects all cherries from that cell (if both visit the same cell, the cherries are collected only once). The objective is to maximize the total cherries collected by both robots once they reach the bottom row.

Key Insights

  • The problem can be modeled as a dynamic programming challenge with state parameters: current row, Robot #1's column, and Robot #2's column.
  • For each state, consider all 9 possible pairs of moves (each robot has 3 possible moves).
  • Use memoization to save and reuse results for subproblems to avoid redundant calculations.
  • Handle the special case when both robots land in the same cell to avoid double counting the cherries.

Space and Time Complexity

Time Complexity: O(rows * cols^2) because there are rows * cols * cols states and each state considers up to 9 transitions.
Space Complexity: O(rows * cols^2) for the memoization or DP table.

Solution

This solution uses a top-down memoized dynamic programming approach. We define a DP state by row index and the columns occupied by the two robots. The recursive function dp(row, col1, col2) returns the maximum number of cherries that can be collected starting from that state to the bottom of the grid. For each state, we try all combinations of moves for both robots. If the two robots land in the same cell, we count cherries only once; otherwise, we sum the values from both cells. The memoization cache ensures that each state is computed only once, leading to an efficient solution even for large grid sizes.

Code Solutions

def cherryPickup(grid):
    rows, cols = len(grid), len(grid[0])
    # memo dictionary to store computed states: key = (row, col1, col2)
    memo = {}

    def dp(row, col1, col2):
        # Out of bound check for either robot.
        if col1 < 0 or col1 >= cols or col2 < 0 or col2 >= cols:
            return float('-inf')
        # Base case: last row collection.
        if row == rows - 1:
            return grid[row][col1] if col1 == col2 else grid[row][col1] + grid[row][col2]
        if (row, col1, col2) in memo:
            return memo[(row, col1, col2)]
        # Collect cherries for current row (avoid double counting if same cell).
        result = grid[row][col1] if col1 == col2 else grid[row][col1] + grid[row][col2]
        best = float('-inf')
        # Explore all possible moves for both robots.
        for d1 in [-1, 0, 1]:
            for d2 in [-1, 0, 1]:
                best = max(best, dp(row + 1, col1 + d1, col2 + d2))
        memo[(row, col1, col2)] = result + best
        return memo[(row, col1, col2)]
    
    return dp(0, 0, cols - 1)

# Example usage:
grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
print(cherryPickup(grid))
← Back to All Questions