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

Find the Maximum Number of Fruits Collected

Difficulty: Hard

Problem Description

In a game dungeon represented as an n x n grid, three children start at the corners (0, 0), (0, n - 1), and (n - 1, 0) and must reach the bottom-right corner (n - 1, n - 1) by making exactly n - 1 moves. Each room contains a certain number of fruits. The goal is to determine the maximum number of fruits that can be collected by the children following specific movement rules.

Key Insights

  • Each child has a unique movement pattern, allowing them to traverse the grid in different ways.
  • The paths of the children may overlap, meaning that fruit collection should account for shared rooms.
  • Dynamic programming can be used to efficiently compute the maximum fruits collected as the children move through the grid.

Space and Time Complexity

Time Complexity: O(n^3) - We need to consider each child's movements and their potential overlaps while traversing the grid. Space Complexity: O(n^2) - A 2D array is used to store the maximum fruits collected at each step for the children.

Solution

To solve this problem, we use a dynamic programming approach. We define a 3D array dp[x][y1][y2] where:

  • x is the current row index.
  • y1 is the column index for the first child.
  • y2 is the column index for the second child.

The value of dp[x][y1][y2] represents the maximum fruits collected when the first child is at (x, y1) and the second child is at (x, y2). The third child can be inferred from the positions of the first two children.

The algorithm proceeds as follows:

  1. Initialize the dynamic programming table.
  2. Iterate through each row and for each possible column positions for the first two children.
  3. Calculate the maximum fruits collected for each combination of positions considering the movements allowed for each child.
  4. Return the maximum fruits collected when all children reach the last row.

Code Solutions

def maxFruits(fruits):
    n = len(fruits)
    dp = [[[0] * n for _ in range(n)] for _ in range(n)]
    
    # Initialize the starting positions
    dp[0][0][n - 1] = fruits[0][0] + fruits[0][n - 1]
    
    for x in range(1, n):
        for y1 in range(max(0, x - 1), min(n, x + 1)):
            for y2 in range(max(0, n - 1 - (x - 1)), min(n, n - 1 + (x + 1))):
                current_fruits = fruits[x][y1] + fruits[x][y2]
                if y1 == y2:
                    current_fruits -= fruits[x][y1]  # Don't double count
                
                # Transition from previous row's positions
                for dy1 in [-1, 0, 1]:
                    for dy2 in [-1, 0, 1]:
                        prev_y1 = y1 - dy1
                        prev_y2 = y2 - dy2
                        if 0 <= prev_y1 < n and 0 <= prev_y2 < n:
                            dp[x][y1][y2] = max(dp[x][y1][y2], dp[x - 1][prev_y1][prev_y2] + current_fruits)
    
    # Find the maximum fruits collected in the last row
    max_fruits = 0
    for y1 in range(n):
        for y2 in range(n):
            max_fruits = max(max_fruits, dp[n - 1][y1][y2])
    
    return max_fruits
← Back to All Questions