C++/Python O(n * n)
Sounds like a search problem. Try a stone from each side, and recursively calculate the difference. Maximize the difference among two choices to play optimally.
Sounds like a search problem. Try a stone from each side, and recursively calculate the difference. Maximize the difference among two choices to play optimally. \n\nWe can memoise the results for the start (`i`) and end(`j`) of the remaining stones.\n\n**C++**\n```cpp\nint dp[1001][1001] = {};\nint dfs(vector<int>& s, int i, int j, int sum) {\n    if (i == j)\n        return 0;\n    return dp[i][j] ? dp[i][j] : dp[i][j] = max(sum - s[i] - dfs(s, i + 1, j, sum - s[i]),\n        sum - s[j] - dfs(s, i, j - 1, sum - s[j]));\n}\nint stoneGameVII(vector<int>& s) {\n    return dfs(s, 0, s.size() - 1, accumulate(begin(s), end(s), 0));\n}\n```\n**Python, Recursion**\nIt looks like something going on with Python on LeetCode, folks need to do manual memo to get it accepted.\n\n> I added the tabulation solution below, its runtime is twice as fast as of the recursive solution.\n\nHere, we are using the prefix sum array to get the subarray sum in O(1). We are not passing the remaining sum as a parameters (like in C++ code above), so it\'s easier to replace manual memo with` @lru_cache(None)`.\n\n```python\nclass Solution:\n    def stoneGameVII(self, s: List[int]) -> int:\n        dp = [[0] * len(s) for _ in range(len(s))]\n        p_sum = [0] + list(accumulate(s))\n        def dfs(i: int, j: int) -> int:\n            if i == j:\n                return 0\n            if dp[i][j] == 0:\n                sum = p_sum[j + 1] - p_sum[i]\n                dp[i][j] = max(sum - s[i] - dfs(i + 1, j), sum - s[j] - dfs(i, j - 1))\n            return dp[i][j]\n        res = dfs(0, len(s) - 1)\n        return res\n\n```\n\n**Python, Tabulation**\n```python\nclass Solution:\n    def stoneGameVII(self, s: List[int]) -> int:\n        dp = [[0] * len(s) for _ in range(len(s))]\n        p_sum = [0] + list(accumulate(s))\n        for i in range(len(s) - 2, -1, -1):\n            for j in range(i + 1, len(s)):\n                dp[i][j] = max(p_sum[j + 1] - p_sum[i + 1] - dp[i + 1][j], \n                               p_sum[j] - p_sum[i] - dp[i][j - 1]);\n        return dp[0][len(s) - 1]\n```
[]