[Python] dp O(N^7) -> O(N^2) beats 100%
O(N^7):\nIn our first dp solution we have 7 variables in our state:\n\n(a,b) : position of player 1\n(c,d) : position of player 2\n(e,f) : position of player 3\
# O(N^7):\nIn our first dp solution we have 7 variables in our state:\n\n(a,b) : position of player 1\n(c,d) : position of player 2\n(e,f) : position of player 3\nsteps: the amount of steps left to the target square\n\nWe prune the search space by disregarding positions where one player position is outside the possible chebychev distance from the target square.\n\n```python\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:\n        n=len(fruits)\n\n        @cache\n        def dp(a,b,c,d,e,f,steps):\n            res=-float("inf")\n            if max(n-1-a,n-1-b)>(n-1-steps) or max(n-1-b,n-1-c)>(n-1-steps) or max(n-1-d,n-1-e)>(n-1-steps): return res\n            if steps==n-1: return sum(fruits[fr][to] for (fr,to) in {(a,b),(c,d),(e,f)})\n            else:\n                for da, db in ((a+1,b+1),(a+1,b),(a,b+1)):\n                    for dc, dd in ((c+1,d-1),(c+1,d),(c+1,d+1)):\n                        for de, df in ((e-1,f+1),(e,f+1),(e+1,f+1)):\n                            if all(0<=foo<n for foo in (da,db,dc,dd,de,df)):\n                                res=max(sum(fruits[fr][to] for (fr,to) in {(a,b),(c,d),(e,f)})+dp(da,db,dc,dd,de,df,steps+1),res)\n            return res\n        return dp(0,0,0,n-1,n-1,0,0)\n```\n\n# O(N^5):\n\nActually, given the constraints we can ignore the first player, because he has to walk on the diagonal to reach the goal. Everytime player 2 or 3 steps on the diagonal, we don\'t count the value and at the diagonal sum separately at the end.\n\n```python\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:\n        n=len(fruits)\n\n        @cache\n        def dp(a,b,e,f,steps):\n            res=-float("inf")\n            if max(n-1-a,n-1-b)>(n-1-steps) or max(n-1-e,n-1-f)>(n-1-steps): return res\n            if steps==n-1: return sum(fruits[fr][to] if fr!=to else 0 for (fr,to) in {(a,b),(e,f)})\n            else:\n                for da, db in ((a+1,b-1),(a+1,b),(a+1,b+1)):\n                        for de, df in ((e-1,f+1),(e,f+1),(e+1,f+1)):\n                            if all(0<=foo<n for foo in (da,db,de,df)):\n                                res=max(sum(fruits[fr][to] if fr!=to else 0 for (fr,to) in {(a,b),(e,f)})+dp(da,db,de,df,steps+1),res)\n            return res\n        return dp(0,n-1,n-1,0,0) + sum(fruits[i][i] for i in range(n))\n```\n\n# O(N^2):\n\nAt this time I got really frustrated and almost wanted to throw in the towel but then I realised that first: the amount of steps is actually already included in a and f, because the players must make a step closer to the target square each time. So we can ditch the step variable. The last optimization comes from splitting the dp function in to two. The second and third player actually never interact with each other.\n\n```python\nclass Solution:\n    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:\n        n=len(fruits)\n\n        @cache\n        def dp1(a,b):\n            res=-float("inf")\n            if max(n-1-a,n-1-b)>(n-1-a): return res\n            if a== n-1: return fruits[a][b]  if a!=b else 0\n            else:\n                for da, db in ((a+1,b-1),(a+1,b),(a+1,b+1)):\n                    if all(0<=foo<n for foo in (da,db)):\n                            res=max((fruits[a][b] if a!=b else 0) +dp1(da,db),res)\n            return res\n        @cache\n        def dp2(e,a):\n            res=-float("inf")\n            if max(n-1-a,n-1-e)>(n-1-a): return res\n            if a==n-1: return fruits[e][a] if e!=a else 0\n            else:\n                for de, df in ((e-1,a+1),(e,a+1),(e+1,a+1)):\n                    if all(0<=foo<n for foo in (de,df)):\n                        res=max((fruits[e][a] if e!=a else 0)+dp2(de,df),res)\n            return res\n        return dp2(n-1,0)+dp1(0,n-1)+sum(fruits[i][i] for i in range(n))\n```\n![grafik.png](https://assets.leetcode.com/users/images/961923f7-e5ad-4196-8c6c-15b8f0161351_1732379645.206869.png)\n\n
['Python3']