Possible Paths
Intuition\n Describe your first thoughts on how to solve this problem. \nIf you read carefully you can tell that first child (0,0) can only take the diagonal pa
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf you read carefully you can tell that first child (0,0) can only take the diagonal path.\nFor other 2 we\'d have to check all possible paths (using dp).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor checking the possible paths for other 2 children, make sure they can reach bottom right with remaining possible moves (total allowed moves are n-1)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O (n^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O (n^2)\n\n# Code\n```python3 []\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:\n        n = len(fruits)\n        res = 0\n        for i in range(n):\n            res+=fruits[i][i]\n        def dist(x,y,m):\n            return max(n-1-x, n-1-y)==n-1-m\n        cache = {}\n        def child(i,j,m, dirs):\n            nonlocal n\n            if (i,j) in cache:\n                return cache[(i,j)]\n            if i==j==n-1:\n                return 0\n            ans = 0\n            for x,y in dirs:\n                if 0<=i+x<n and 0<=j+y<n and dist(i+x, j+y, m+1):\n                    v = fruits[i][j] if i!=j else 0\n                    ans = max(ans, v + child(i+x, j+y, m+1, dirs))\n            cache[(i,j)] = ans\n            return ans\n        res+=child(n-1, 0, 0, [[1,1], [-1,1], [0,1]])\n        res+=child(0,n-1,0, [[1,1],[1,-1],[1,0]])\n        return res\n```
['Python3']