Easy Dp
Child 1 can only go along the diagonal made this question way too easy \n\n# Code\npython3 []\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[Li
Child 1 can only go along the diagonal made this question way too easy \n\n# Code\n```python3 []\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:\n        n = len(fruits)\n        res = sum(fruits[i][i] for i in range(n))\n        @cache\n        def dp1(i,j):\n            if i == n-1 and j == n-1:\n                return 0\n            elif i>=j:return -inf\n            res = 0\n            for ni,nj in [(i+1,j-1),(i+1,j),(i+1,j+1)]:\n                if 0<=ni<n and 0<=nj<n:\n                    res = max(res,fruits[i][j]+dp1(ni,nj))\n            return res\n        @cache\n        def dp2(i,j):\n            if i == n-1 and j == n-1:\n                return 0\n            elif i<=j:return -inf\n            res = 0\n            for ni,nj in [(i-1,j+1),(i,j+1),(i+1,j+1)]:\n                if 0<=ni<n and 0<=nj<n:\n                    res = max(res,fruits[i][j]+dp2(ni,nj))\n            return res\n        return res + dp1(0,n-1)+dp2(n-1,0)\n        \n```
['Dynamic Programming', 'Python3']