Python || Beginner Friendly Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nA child can take only "n-1" steps. That means\n\n1. Child starting at (0, 0): diagona
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nA child can take only "n-1" steps. That means\n\n1. Child starting at (0, 0): diagonal is the only path they can take\n2. Child starting at (n-1, 0): maximum path for this child cannot be found beyond lower half of the matrix\n3. Child starting at (0, n-1): maximum path for this child cannot be found beyond upper half of the matrix\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCalculate maximum fruits for each child separately.\n\nMaximum fruits in a path could be calculated using DFS. To simplify DFS travesal, only consider the specific part(either upper half or lwoer half) of the matrix.\n\n# Complexity\n- Time complexity:\nO(n^2)\n\n- Space complexity:\nO(n^2)\n\n# Code\n```python3 []\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:\n\n        @cache\n        def maxFruits(i, j, steps):\n            if i == n-1 and j == n-1:\n                return 0\n            if steps == 0:\n                return -math.inf\n            ans = 0\n            for d1, d2 in dirs:\n                x = i + d1\n                y = j + d2\n                if 0 <= x < n and 0 <= y < n:\n                    ans = max(ans, grid[x][y] + maxFruits(x, y, steps-1))\n            return ans\n        \n        n = len(fruits)\n        res = sum([fruits[i][i] for i in range(n)])\n        \n        # calculate maximum fruits for child in upper half\n        dirs = [[1, -1], [1, 0], [1, 1]]\n        grid = [[0 for _ in range(n)] for _ in range(n)]\n        for i in range(n):\n            for j in range(i+1, n):\n                grid[i][j] = fruits[i][j]\n        res += fruits[0][n-1] + maxFruits(0, n-1, n-1)\n\n        # calculate maximum fruits for child in lower half\n        dirs = [[-1, 1], [0, 1], [1, 1]]\n        grid = [[0 for _ in range(n)] for _ in range(n)]\n        for j in range(n):\n            for i in range(j+1, n):\n                grid[i][j] = fruits[i][j]\n        res += fruits[n-1][0] + maxFruits(n-1, 0, n-1)\n\n        return res\n\n\n\n        \n```
['Python3']