Python3. DP without prefix sum.
Idea: make moves of two players as one dp step.\nThere are 4 cases. Consider [a, b, c, x, y, z]. \n1. Player one takes a. \n\t1.1. Player two takes b. Score sum
Idea: make moves of two players as one dp step.\nThere are 4 cases. Consider `[a, b, c, x, y, z]`. \n1. Player one takes `a`. \n\t1.1. Player two takes `b`. Score `sum(b, c, x, y, z) - sum(c, x, y, z) = b`.\n\t1.2. Player two takes `z`. Score `sum(b, c, x, y, z) - sum(b, c, x, y) = z`.\n2. Player one takes `z`.\n\t2.1. Player two takes `y`. Score `sum(a, b, c, x, y) - sum(a, b, c, x) = y`.\n\t2.2. Player two takes `a`. Score `sum(a, b, c, x, y) - sum(b, c, x, y) = a`.\n\nSo after two moves score equals to one element (that was taken by second player) from input array. Every two moves score increases by one of array elements. That way we don\'t need prefix sums.\n\n```\nclass Solution:\n    def stoneGameVII(self, stones: List[int]) -> int:\n        @lru_cache(None)\n        def dp(i, j):\n            if i >= j:\n                return 0\n\t\t\t# maximize by first player and minimize by the second one\n            return max(\n                min(stones[i + 1] + dp(i + 2, j), stones[j] + dp(i + 1, j - 1)),\n                min(stones[j - 1] + dp(i, j - 2), stones[i] + dp(i + 1, j - 1))\n            )\n        return dp(0, len(stones) - 1)\n```
[]