3648. Find the Maximum Number of Fruits Collected

class Solution:
    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
        n = len(fruits)
        
        # Child 1 from (0,0) to (n-1,n-1): must go along diagonal
        # Path is fixed: (0,0) -> (1,1) -> ... -> (n-1,n-1)
        child1 = sum(fruits[i][i] for i in range(n))
        
        # Child 2 from (0, n-1) to (n-1, n-1)
        # Can move: (i+1, j-1), (i+1, j), (i+1, j+1) but also (i, j+1) mentioned
        # Actually based on problem: move to (i+1, j+1), (i+1, j), (i, j+1)
        # Let me re-read: from (0, n-1) moves are (i+1, j-1), (i+1, j), (i+1, j+1)
        # But needs to reach (n-1, n-1) in n-1 steps
        
        # For child from (0, n-1): starts at col n-1, needs to reach col n-1
        # Can only move down: (i+1, j-1), (i+1, j), (i+1, j+1)
        # But can't go beyond column n-1
        
        # Child 2 DP: dp2[i][j] = max fruits collected reaching (i, j)
        INF = float('-inf')
        dp2 = [[INF] * n for _ in range(n)]
        dp2[0][n-1] = fruits[0][n-1]
        
        for i in range(1, n):
            for j in range(n):
                # Can come from (i-1, j-1), (i-1, j), (i-1, j+1)
                for dj in [-1, 0, 1]:
                    pj = j + dj
                    if 0 <= pj < n and dp2[i-1][pj] != INF:
                        # Child 2 cannot visit diagonal cells (except start and end)
                        # because child 1 visits them
                        if j <= i or (i == n-1 and j == n-1):
                            # Invalid: would be on or left of diagonal before reaching end
                            # Actually child 2 stays in upper-right triangle
                            continue
                        dp2[i][j] = max(dp2[i][j], dp2[i-1][pj] + fruits[i][j])
        
        # Actually let me reconsider the constraints
        # Child 2 starts at (0, n-1) and goes to (n-1, n-1)
        # Must stay in region j > i (upper right, excluding diagonal) until reaching (n-1, n-1)
        
        # Reset and redo
        dp2 = [[INF] * n for _ in range(n)]
        dp2[0][n-1] = 0  # Start doesn't get counted (will add separately)
        
        for i in range(1, n):
            for j in range(i + 1, n):  # j > i, stay right of diagonal
                for dj in [-1, 0, 1]:
                    pj = j + dj
                    if i - 1 < pj < n and dp2[i-1][pj] != INF:
                        dp2[i][j] = max(dp2[i][j], dp2[i-1][pj] + fruits[i][j])
        
        # Final step to (n-1, n-1) - this is on diagonal, allowed
        child2 = 0
        for dj in [-1, 0, 1]:
            pj = n - 1 + dj
            if n - 2 < pj < n and dp2[n-2][pj] != INF:
                child2 = max(child2, dp2[n-2][pj])
        child2 += fruits[0][n-1]  # Add starting cell
        
        # Child 3 from (n-1, 0) to (n-1, n-1)
        # Can move: (i-1, j+1), (i, j+1), (i+1, j+1)
        # Must stay below diagonal (i > j)
        dp3 = [[INF] * n for _ in range(n)]
        dp3[n-1][0] = 0
        
        for j in range(1, n):
            for i in range(j + 1, n):  # i > j, stay below diagonal
                for di in [-1, 0, 1]:
                    pi = i + di
                    if j - 1 < pi < n and dp3[pi][j-1] != INF:
                        dp3[i][j] = max(dp3[i][j], dp3[pi][j-1] + fruits[i][j])
        
        child3 = 0
        for di in [-1, 0, 1]:
            pi = n - 1 + di
            if n - 2 < pi < n and dp3[pi][n-2] != INF:
                child3 = max(child3, dp3[pi][n-2])
        child3 += fruits[n-1][0]  # Add starting cell
        
        return child1 + child2 + child3