Unfriendly to python, why my python O(n^2) topdown dp got MLE;
conclusion\n\ndiff\nclass Solution:\n    def stoneGameVII(self,A) -> int:\n        n = len(A)\n        @lru_cache(None)\n        def dp(i,j):\n            if j-
## conclusion\n\n```diff\nclass Solution:\n    def stoneGameVII(self,A) -> int:\n        n = len(A)\n        @lru_cache(None)\n        def dp(i,j):\n            if j-i+1<=0: return 0\n            if (j-i+1) %2 == n%2: return max(dp(i+1,j),dp(i,j-1))\n            return min(A[i]+dp(i+1,j),A[j]+dp(i,j-1))\n-       return dp(0,n-1)\n+       ret = dp(0,n-1)\n+       del dp # or `dp.cache_clear()`\n+       return ret\n```\n\n## main part\n-----\n\nWhy my python O(n^2) topdown dp got MLE(**(2020, 12, 17)currently it\'s TLE**) if I use a `2d dict` or use `@lru_cache(None)`?\n\n```\nclass Solution:\n    def stoneGameVII(self,A) -> int:\n        n = len(A)\n        cac = {}\n        def dp(i,j):\n            """\n            if (j-i+1) %2 == n%2, Alice choose first; \n\t\t\totherwise Bob choose first.\n            return the maximum difference of Alice score - Bob score, choosing from A[i:j+1], by playing stoneGameVII\n\t\t\tI don\'t want to explain why this algorithm is correct, this is what I submit on the contest. \n\t\t\tThe main point is why MLE/TLE.\n\t\t\tCompare to dp using prefix sum, this algorithm is obscure and not recommend\n            """\n            if (i,j) not in cac:\n                if j-i+1<=0: return 0\n                if (j-i+1) %2 == n%2:\n                    # Alice choose, but what she choose don\'t credit to return value\n                    r = max(dp(i+1,j),dp(i,j-1))\n                else:\n                    # Bob choose\n                    r = min(A[i]+dp(i+1,j),A[j]+dp(i,j-1))\n                cac[i,j]=r\n                return r\n            else:\n                return cac[i,j]\n        return dp(0,n-1)\n```\n\t\n~~I know I can change that to 1d dp, but this is really the first time I need to use dp space compression in a contest.~~\n\n-----\nLeetcodeOJ create a `Solution` object for every testcases, in order to solve this problem, there are serveral ways:\n+ <b> combine `@lru_cache(None)` with `.cache_clear()` or `del` topdown function </b>\n+ `import gc; gc.collect()`\n+ `del` the data structure at the end of a method or call the `.clear()` method of the memorization hashdict\n+ change to a space 1d topdown dp if possible(`@lru_cache(n)` check example code below)\n+ use another dp status calculation order\n    + bottom-up dp\n\t+ bfs order, store status layer by layer(if possible, such as #1770)\n+ ~~change to c++ or java~~\n\nBelow is a table record my experiment results based on python3.  This experiment result happens in a specific time point, the results are expected to has the same runtime and memory as if the same code was submitted on weekly contest 219, currently maybe the OJ have added more testcases so the experiment results can\'t repeated.\nYou can find some code at the bottom of this post.\nI don\'t know why `dict` maybe TLE when declared as a global variable.\n\n|runtime(s)/memory(MB) |(no action)|`del` operator or<sup>[1][f1]</sup> <br>`clear()` method<sup>[2][f2]</sup> or `cache_clear()` method<sup>[3][f3]</sup>|global|`__init__`<sup>[4][f4]</sup>|\n|---|---|---|---|---|---|\ntopdown `lru_cache(None)`|MLE|5.8/111|~~--------------~~|~~--------------~~\ntopdown  2d list|5.9/89|6/32|6.4/32|9.1/94\ntopdown 2d dict|MLE|7.3/111|TLE or 7.3/111|TLE or 7.2/111\nbottomup 2d list|3.9/30|3.9/30|5/30|4.7/30\n\nFor those code cost memory <20 MB above methods are not meaningful.\n\n[f1]: # (only slightly difference)\n[f2]: # (combined with dict or list)\n[f3]: # (combined with lru_cache)\n[f4]: # (declare in `Solution.__init__` function )\n\n<details><summary>A space 1d dp code:(14.5 MB)</summary>\n<p>\n\n```\nclass Solution:\n    def stoneGameVII(self,A) -> int:\n        n = len(A)\n        dp=[0]*(n+1)\n        for j in range(n):\n            for ri in range(n-j,n+1):\n                i=n-ri\n                assert 0<=i<=j\n                if (j-i+1)%2==n%2:\n                    dp[ri]=max(dp[ri-1] if ri>=1 else 0,dp[ri])\n                else:\n                    dp[ri]=min(A[i]+(dp[ri-1] if ri>=1 else 0) ,A[j]+dp[ri])\n        return dp[n]\n```\n\n</p>\n</details>\n\n<details>\n\n<summary>Use lru_cache(n+10) code (17 MB)</summary>\n Since this can be reduced to a space 1d dp you can use `lru_cache(maxsize=n+10)`  by a proper function calling sequence.\n Ensure(at least in my code) calling `dp(i+1,j)` before calling `dp(i,j-1)`, otherwise you will got a TLE. \n<p>\n\n```\ndef stoneGameVII(self,A) -> int:\n    n = len(A)\n    @lru_cache(maxsize=n+10)\n    def dp(i,j):\n        if j-i+1<=0: return 0\n        if (j-i+1) %2 == n%2:\n            return max(dp(i+1,j),dp(i,j-1))\n        else:\n            return min(A[i]+dp(i+1,j),A[j]+dp(i,j-1))\n\n    return dp(0,n-1)\n```\n<blockquote>\n<details><summary>A TLE test code mentioned above</summary>\n<p>\n\n```\nclass Solution:\n    def stoneGameVII(self,A) -> int:\n        n = len(A)\n        @lru_cache(maxsize=3000)\n        def dp(i,j):\n            if j-i+1<=0: return 0\n            if (j-i+1) %2 == n%2:\n                return max(dp(i,j-1),dp(i+1,j))\n            else:\n                return min(A[i]+dp(i+1,j),A[j]+dp(i,j-1))\n\n        return dp(0,n-1)\n```\n</p>\n</details>\n</blockquote>\n\n</p></details>\n\n<details><summary>A global 2d dict TLE code</summary><p>\n\n```\ncac = {}\nclass Solution:\n    def stoneGameVII(self,A) -> int:\n        n = len(A)\n        def dp(i,j):\n            if (i,j) not in cac:\n                if j-i+1<=0: return 0\n                if (j-i+1) %2 == n%2:\n                    r = max(dp(i+1,j),dp(i,j-1))\n                else:\n                    r = min(A[i]+dp(i+1,j),A[j]+dp(i,j-1))\n                cac[i,j]=r\n                return r\n            else:\n                return cac[i,j]\n        r = dp(0,n-1)\n        cac.clear()\n        return r\n```\n</p>\n</details>\n\n<details><summary>A global 2d dict AC code</summary><p>\n\n```\ncac = {}\nclass Solution:\n    def stoneGameVII(self,A) -> int:\n        cac.clear()\n        n = len(A)\n        def dp(i,j):\n            if (i,j) not in cac:\n                if j-i+1<=0: return 0\n                if (j-i+1) %2 == n%2:\n                    r = max(dp(i+1,j),dp(i,j-1))\n                else:\n                    r = min(A[i]+dp(i+1,j),A[j]+dp(i,j-1))\n                cac[i,j]=r\n                return r\n            else:\n                return cac[i,j]\n        return dp(0,n-1)\n```\n</p>\n</details>\n\n<details><summary>`__init__` 2d dict AC</summary><p>\n\n```\nclass Solution:\n    def __init__(self):\n        self.cac = {}\n    def stoneGameVII(self,A) -> int:\n        cac = self.cac\n        n = len(A)\n        def dp(i,j):\n            if (i,j) not in cac:\n                if j-i+1<=0: return 0\n                if (j-i+1) %2 == n%2:\n                    r = max(dp(i+1,j),dp(i,j-1))\n                else:\n                    r = min(A[i]+dp(i+1,j),A[j]+dp(i,j-1))\n                cac[i,j]=r\n                return r\n            else:\n                return cac[i,j]\n        r = dp(0,n-1)\n        cac.clear()\n        return r\n```\n</p></details>\n\n<details><summary>`__init__` 2d dict TLE</summary><p>\n\n```\nclass Solution:\n    def __init__(self):\n        self.cac = {}\n    def stoneGameVII(self,A) -> int:\n        cac = self.cac\n        cac.clear()\n        n = len(A)\n        def dp(i,j):\n            if (i,j) not in cac:\n                if j-i+1<=0: return 0\n                if (j-i+1) %2 == n%2:\n                    r = max(dp(i+1,j),dp(i,j-1))\n                else:\n                    r = min(A[i]+dp(i+1,j),A[j]+dp(i,j-1))\n                cac[i,j]=r\n                return r\n            else:\n                return cac[i,j]\n        r = dp(0,n-1)\n        \n        return r\n```\n</p></details>\n\n## similar python topdown TLE problem\n#516. Longest Palindromic Subsequence\n#1770. Maximum Score from Performing Multiplication Operations\n\n----\nThanks to @rowe1227 @infmount .
[]