[Python] O(n*n) dp solution, how to avoid TLE, explained
We can see dynamic programming structure in this problem: each time we take some stones from the left or from the left side, what is rest is always contigious a
We can see dynamic programming structure in this problem: each time we take some stones from the left or from the left side, what is rest is always contigious array. So, let us denote by `dp(i, j)` the biggest difference in scores for the person who start with this position.\n\n1. If `i > j`, then we have empty array and result is zero.\n2. In the opposite case, we have two options: we can take either leftmost stone or rightmost stone. We also precomputed `CSum`: cumulative sums to evaluate sums in ranges in `O(1)` time. We can either can gain sum from `[i+1, j]` and subtract `dp(i+1, j)` or we can gain sum from `[i, j-1]` and subtract `dp(i, j-1)`. Why we need to subtract here? Because `dp(i+1, j)` and `dp(i, j-1)` is maximum difference of scores **another** player can gain, so for current player we need to take negative value.\n\n#### Complexity\nWe have `O(n^2)` states with `2` transactions from every state, so total time and space is `O(n^2)`.\n\n#### Code\n```python\nclass Solution:\n    def stoneGameVII(self, A):\n        CSum = [0] + list(accumulate(A))\n        @lru_cache(2000)\n        def dp(i, j):\n            if i > j: return 0\n            sm = CSum[j + 1] - CSum[i]\n            return sm - min(A[i] + dp(i+1, j), A[j] + dp(i, j-1))\n        \n        return dp(0, len(A) - 1)\n```\n\n#### Important remark\nSometimes when we use `lru_cache`, it works slower than memoisation by hands, and in this problem you will get TLE if you use usual `@lru_cache(None)`, because restrictions in this problem are quite tight on python. So, what you can do during contest to avoid this?\n1. Do memorisation by hands: it is the quickest and working way to do it: instead of `lru_cache`, use say dictionary `d` and each time in the beginning check if we have element in `d` or not.\n2. Change `None` in `lru_cache` to some magical constant, here `1000` to `10000` will work fine, but I do not have explanation why. And on the contest you can not be lucky to get it or you get it and then it will be rejudged and you will get TLE or MLE. So, it is not safe in my opinion.\n3. Use classical table dp, where you have here `2d` list of lists and then fill it with usual ways. It is also safe way, but I am so used to `lru_cache`, so for this one I would have spend more time on contest, but if method `1` is not working, you should definitely go to this one.\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']