DP || Recursive || Python
The 2 children at (0,n-1) and (n-1,0) dont intersect at any moment of their travel. They only intersect at the diagonal but it doesn\'t matter as we will have t
The 2 children at (0,n-1) and (n-1,0) dont intersect at any moment of their travel. They only intersect at the diagonal but it doesn\'t matter as we will have to forcefully give all diagonal elements to the first child starting from (0,0) otherwise his moves will exceed n-1. Hence this problem has now boiled down to 2 independent problems of child starting at each of (0,n-1) and (n-1,0) on the same grid. Rest is simple recursive dp for child at (0,n-1) and child at (n-1,0). Finally add diagonal contribution of first child.\nTime Complexity - O(n * n)\nSpace Complexity - O(n * n)\n\nCode:\n\n```\nclass Solution:\n    def maxCollectedFruits(self, grid: List[List[int]]) -> int:\n        ans,n=0,len(grid)\n        for i in range(n): ans+=grid[i][i]; grid[i][i]=0;\n        d1,d2=((0,1),(-1,1),(1,1)),((1,0),(1,1),(1,-1))\n        @cache\n        def dp1(i,j):\n            if j==n-1: return grid[i][j] if i==n-1 else -sys.maxsize\n            res=-sys.maxsize\n            for di,dj in d1:\n                ni,nj=i+di,j+dj\n                if not (0<=ni<n) or not (0<=nj<n): continue\n                res=max(res,dp1(ni,nj))\n            return res+grid[i][j]\n        @cache\n        def dp2(i,j):\n            if i==n-1: return grid[i][j] if j==n-1 else -sys.maxsize\n            res=-sys.maxsize\n            for di,dj in d2:\n                ni,nj=i+di,j+dj\n                if not (0<=ni<n) or not (0<=nj<n): continue\n                res=max(res,dp2(ni,nj))\n            return res+grid[i][j]\n        return ans+dp1(n-1,0)+dp2(0,n-1)\n        \n            \n        \n        \n```
['Dynamic Programming', 'Greedy', 'Python3']