[Python] Space optimized DP: 99% speed
This problem is almost equivalent to problem 486, and even has the same DP equation:\nDP[i][j] is the difference in scores between the next player to move and t
This problem is almost equivalent to [problem 486](https://leetcode.com/problems/predict-the-winner/), and even has the same DP equation:\nDP[i][j] is the difference in scores between the next player to move and the other player on the array stones[i .. j]. Then we get\nDP[i][j] = max(score for choosing i - DP[i+1][j], score for choosing j - DP[i][j-1]).\nThe only difference is that score for choosing i is now sum(stones[i..j]) - stones[i]: we still want to know DP[0][n-1]\n\nUsing the 1D dp trick (only store the last row) and computing prefix sums on the fly, we get O(n^2) time, O(n) space:\n\n```python\ndef stoneGameVII(self, stones: List[int]) -> int:\n\tn = len(stones)\n\tdp = [0] * n\n\n\tfor i in range(n - 1, -1, -1):\n\t\tv = stones[i]\n\t\trun_sum = 0\n\n\t\tfor j in range(i + 1, n):\n\t\t\tnew_run = run_sum+stones[j]\n\t\t\tdp[j] = max(new_run - dp[j], run_sum+v - dp[j - 1])\n\t\t\trun_sum = new_run\n\treturn dp[n - 1]\n```
['Dynamic Programming', 'Python']