O(N^2) DP in Python, Faster than 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe key is the children should move in exact $n-1$ steps. As a result, the child starte
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key is the children should move in exact $n-1$ steps. As a result, the child started from `(0, 0)` can only move in the diagonal, while the other two children cannot move across the diagonal. \nIf the children from `(0, n-1)` and `(n-1, 0)` move across the diagonal, they can never reach the target cell `(n-1, n-1)` according to their move patterns. In addition, they never should move to a cell on the diagonal since the cell will be always taken by the diagonal child. So, the child from `(0, n-1)` can explore only the upper right part of the matrix; the child from `(n-1, 0)` can explore only the lower left part of the matrix, and all the cells on the diagonal will be taken by the child from `(0, 0)`. \n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBased on the observation, we can split the grid into three independent areas: diagonal, upper right, and lower left. Then, the classic picking-up DP can be used to find the most amount of fruits for the child from `(0, n-1)` to `(n-2, n-1)` and the child from `(n-1, 0)` to `(n-1, n-2)`. The final number is the total fruits these three children pick up. \n\n# Complexity\n- Time complexity: $O(n^2)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def maxCollectedFruits(self, grid: List[List[int]]) -> int:\n        n = len(grid)\n        diagonal = sum(grid[i][i] for i in range(n))\n        dp = []\n        for i in range(n):\n            dp.append([-inf] * n)\n        dp[0][n-1] = grid[0][n-1]\n        dp[n-1][0] = grid[n-1][0]\n        for i in range(1, n):\n            for j in range(i+1, n):\n                dp[i][j] = dp[i-1][j] + grid[i][j]\n                dp[j][i] = dp[j][i-1] + grid[j][i]\n                if j + 1 < n:\n                    dp[i][j] = max(dp[i][j], dp[i-1][j+1] + grid[i][j])\n                    dp[j][i] = max(dp[j][i], dp[j+1][i-1] + grid[j][i])\n                if j - 1 >= 0:\n                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + grid[i][j])\n                    dp[j][i] = max(dp[j][i], dp[j-1][i-1] + grid[j][i])\n        return diagonal + dp[n-1][n-2] + dp[n-2][n-1]\n```
['Dynamic Programming', 'Python3']