Simple python3 solution | DP
Approach\n Describe your approach to solving the problem. \nThe first child must walk diagonally. The second and third children can only intersect diagonally.\n
# Approach\n<!-- Describe your approach to solving the problem. -->\nThe first child must walk diagonally. The second and third children can only intersect diagonally.\n\nLet\'s calculate the answer for the first child, zero the diagonal, and calculate the paths of the remaining children independently.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:\n        n = len(fruits)\n        \n        first_child = sum(fruits[i][i] for i in range(n))\n        for i in range(n):\n            fruits[i][i] = 0\n\n        @cache\n        def calc_second_child(x, y):\n            if y < n // 2:\n                return -float(\'inf\')\n                \n            if x == n - 1:\n                if y == n - 1:\n                    return fruits[x][y]\n                return -float(\'inf\')\n            \n            return fruits[x][y] + max(\n                calc_second_child(x + 1, y - 1),\n                calc_second_child(x + 1, y),\n                calc_second_child(x + 1, y + 1) if y != n - 1 else -float(\'inf\'),\n            )\n        \n        @cache\n        def calc_third_child(x, y):\n            if x < n // 2:\n                return -float(\'inf\')\n\n            if y == n - 1:\n                if x == n - 1:\n                    return fruits[x][y]\n                return -float(\'inf\')\n            \n            return fruits[x][y] + max(\n                calc_third_child(x - 1, y + 1),\n                calc_third_child(x, y + 1),\n                calc_third_child(x + 1, y + 1) if x != n - 1 else -float(\'inf\'),\n            )\n\n        return (\n            first_child\n            + calc_second_child(0, n - 1)\n            + calc_third_child(n - 1, 0)\n        )\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Python3']