Python3 || 12 lines, recursion dp  || T/S: 76% / 64%
Here\'s the plan:\n1. We compute the sum of the diagonal.\n1. We compute the optimum answer for the upper triangle with recursive function dp.\n 1. We compute t
Here\'s the plan:\n1. We compute the sum of the diagonal.\n1. We compute the optimum answer for the upper triangle with recursive function dp.\n 1. We compute the optimum answer for the lower triangle by transposing `fruits` (making the lower triangle into an upper triangle) and using dp again.\n \n1. We return the sum of the results of 1-3 above as the solution.\n\n\n```python3 []\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:   \n\n        @lru_cache(9000)\n        def dp(row: int, col: int)-> int:\n\n            if 0 <= col < row < n:                                  \n                return fruits[row][col] + max(dp(row-1, col+1),\n                                              dp(row  , col+1),\n                                              dp(row+1, col+1))\n            return 0\n\n\n        n = len(fruits)\n        diag = sum(map(lambda x:fruits[x][x], range(n)))    # <= 1)\n\n        upper = dp(n - 1, 0)                                # <= 2)\n\n        dp.cache_clear()                                    # <= 3)\n        fruits = list(zip(*fruits))                         # \n                                                            # \n        lower = dp(n - 1, 0)                                # \n\n        return diag + upper + lower                         # <= 4)\n```\n[https://leetcode.com/problems/find-the-maximum-number-of-fruits-collected/submissions/1462776522/](https://leetcode.com/problems/find-the-maximum-number-of-fruits-collected/submissions/1462776522/)\n\nI could be wrong, but I think that time complexity is *O*(*N* ^2) and space complexity is *O*(*N* ^2), in which *N* ~ `len(fruits)`.
['Python3']