Python [Top-down DP]
I think this is a quite difficult question even if the code itself is short. We need to use dynamic programming and in order to avoid tracking the solution path
I think this is a quite difficult question even if the code itself is short. We need to use dynamic programming and in order to avoid tracking the solution path for both Alice and Bob the DP should be on differences. \n\nIf we let `dp(i, j)` to be the best possible move for any player\'s turn, then this depends on selecting the max possible score based on current stones minus the min possible score for the subsequent interval. So unlike most other interval DP problems of sort `dp(i, j) = ... + f(dp(i + 1, j), dp(i, j-1))` here we have `dp(i, j) = ... - f(dp(i + 1, j), dp(i, j-1)` and this sign keeps flipping between calls, making it a max-min problem as expected.\n\nTime: `O(N^2)`\nSpace: `O(N^2)`\nThe complexity is quadratic, as there are N-choose-2 intervals.\n\n**Caution:** There seems to be a platform-specific issue when it comes to python top-down DP using lru_cache. Below I was able to get AC using `lru_cache(65536)` instead of `lru_cache(None)`. \n\n```python\nclass Solution:\n    def stoneGameVII(self, stones):\n        prefix = list(accumulate(stones, initial = 0))\n        \n        @lru_cache(65536)\n        def dp(i, j):\n            if i == j: \n                return 0\n            return max(prefix[j + 1] - prefix[i + 1] - dp(i + 1, j), \\\n                       prefix[j] - prefix[i] - dp(i, j - 1))\n        \n        return dp(0, len(stones) - 1)\n```
[]