Leetcode # 3363. Find the Maximum Number of Fruits Collected

Problem

https://leetcode.com/problems/find-the-maximum-number-of-fruits-collected

Solution: Bottom-Up DP (Tabulation)

• The children will make exactly n - 1 moves to reach the room (n - 1, n - 1)
  ⇒ child_1 只能走在對角線上
  ⇒ child_2, child_3 不可跨過對角線
  　 且不可步進對角線 (一旦踏上對角線，之後只能沿著對角線)
• When a child enters a room, they will collect all the fruits there.
  If two or more children enter the same room, only one child will collect the fruits,
  and the room will be emptied after they leave.

Time Complexity: O(n ** 2)
Space Complexity: O(n ** 2)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
    n, dp = len(fruits), []
    for i in range(n):
      dp.append([-1] * n)
    ans = sum([fruits[i][i] for i in range(n)])

    dp[0][n - 1] = fruits[0][n - 1]
    for i in range(1, n):
      for j in range(n):
        if dp[i - 1][j] < 0:
          continue
        if (_j := j + 1) < n and _j > i:
          dp[i][_j] = max(dp[i][_j], dp[i - 1][j] + fruits[i][_j])
        if i == n - 1 or j > i:
          dp[i][j] = max(dp[i][j], dp[i - 1][j] + fruits[i][j])
        if (_j := j - 1) > 0 and _j > i:
          dp[i][_j] = max(dp[i][_j], dp[i - 1][j] + fruits[i][_j])
    ans += dp[n - 1][n - 1]

    dp[n - 1][n - 1] = -1
    dp[n - 1][0] = fruits[n - 1][0]
    for j in range(1, n):
      for i in range(n):
        if dp[i][j - 1] < 0:
          continue
        if (_i := i + 1) < n and _i > j:
          dp[_i][j] = max(dp[_i][j], dp[i][j - 1] + fruits[_i][j])
        if j == n - 1 or i > j:
          dp[i][j] = max(dp[i][j], dp[i][j - 1] + fruits[i][j])
        if (_i := i - 1) > 0 and _i > j:
          dp[_i][j] = max(dp[_i][j], dp[i][j - 1] + fruits[_i][j])
    ans += dp[n - 1][n - 1]
        
    return ans - 2 * fruits[n - 1][n - 1]

Last Updated on 2025/08/10 by A1go