Tabulation DP (n^2) with clean code and explanation [PYTHON]
Intuition\nFor any n x n grid the length of diagonal is also n, hence to move from (0, 0) to (n - 1, n -1) we will have to follow the diagonal (n-1 steps), if w
# Intuition\nFor any `n x n` grid the length of diagonal is also `n`, hence to move from `(0, 0)` to `(n - 1, n -1)` we will have to follow the diagonal (`n-1` steps), if we do not follow this we will always result in `> n - 1`\n\nFor the point at the bottom, in order to reach `(n-1, n-1)` we can not go beyond the main diagonal , hence we must stay beneath, and it also makes sense to not touch the diagonal (even though we can) since it guaranteed to be covered by the origin child.\n\n# Approach\nDesign a `n x n` dp grid,\n\nTabulate base cases \n\n```\ndp[n - 1][0] = fruits[n - 1][0]\ndp[0][n - 1] = fruits[0][n - 1]\ndp[0][0] = fruits[0][0]\n```\n\n\ncalculate with respect to one of the child , at `(0, n - 1)` or `(n - 1, 0)` then we can use transpose and tabulate the other one\n\nFor now lets go with bottom left child,\n\nfor each column we can calculate the maximum allotted height it can go "UP" which I calculated using `curr = n - 1 - min(i, n - i - 2)` \n\nwhen at column `i` we can keep track of the previous max allotted height it (`prev`) was able to go up at `i-1`, and using that restrict the possible coordinates it could have come from `i-1`\n\nand then its a simple tabulation \n\n```\ndp[j][i] = max(dp[j][i], dp[x][y] + fruits[j][i])\n```\n\nswitch `i <-> j` and `x <-> y`, and we get the tabulation for the transpose of point `(i, j)` which makes things a lot easier.\n\n\n# Complexity\n- Time complexity: $O(n^2)$\n<!-- Add your time complexity here, e.g. $$O(n^2)$$ -->\n\n- Space complexity: $O(n^2)$\n<!-- Add your space complexity here, e.g. $$O(n^2)$$ -->\n\n# Code\n```python3 []\n\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:\n        n = len(fruits)\n        valid = [(0, -1), (-1, -1), (1, -1)]\n        dp = [[0] * n for _ in range(n)]\n        dp[n - 1][0] = fruits[n - 1][0]\n        dp[0][n - 1] = fruits[0][n - 1]\n        dp[0][0] = fruits[0][0]\n\n        prev = n - 1\n        for i in range(1, n):\n            curr = n - 1 - min(i, n - i - 2)\n            for j in range(n - 1, curr - 1, -1):\n                for dx, dy in valid:\n                    x = j + dx\n                    y = i + dy\n                    if prev <= x <= n - 1:\n                        dp[j][i] = max(dp[j][i], dp[x][y] + fruits[j][i])\n                        dp[i][j] = max(dp[i][j], dp[y][x] + fruits[i][j])\n            dp[i][i] = dp[i-1][i-1] + fruits[i][i]\n            prev = curr\n\n\n        return dp[n-1][n-2] + dp[n-2][n-1] + dp[n-1][n-1]\n```
['Python3']