Minimax Approach with Dual Caching for Stone Game VII
\n# Approach\n Describe your approach to solving the problem. \nThis solution applies a minimax algorithm to solve the Stone Game VII problem, utilizing distinc
\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThis solution applies a minimax algorithm to solve the Stone Game VII problem, utilizing distinct caches for Alice and Bob. The approach involves:\n\n- **Prefix Sum Array:** To efficiently calculate the total sum of stones between any two indices.\n- **Dual Caching:** Separate caching (cacheA and cacheB) for Alice and Bob, improving efficiency by storing results of subproblems based on which player is currently making a move.\n- **Minimax Strategy:** Alice tries to maximize the score difference, while Bob tries to minimize it, using a top-down recursion with memoization to avoid redundant computations.\n\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def stoneGameVII(self, stones: List[int]) -> int:\n        n = len(stones)\n\n        prefix = [0]\n        for i in range(n):\n            prefix.append(prefix[-1] + stones[i])\n        \n        has_cacheA = [[False] * n for _ in range(n)]\n        has_cacheB = [[False] * n for _ in range(n)]\n        cacheA = [[0] * n for _ in range(n)]\n        cacheB = [[0] * n for _ in range(n)]\n        \n        def dfs(isAlice, l, r):\n            if l > r: \n                return 0\n\n            if has_cacheA[l][r]:\n                return cacheA[l][r]\n            if has_cacheB[l][r]:\n                return cacheB[l][r]\n\n\n            res = float("-inf") if isAlice else float("inf")\n            # Total sum of the stones between indices l and r\n            total = prefix[r + 1] - prefix[l]\n\n            if isAlice:\n                res = max(\n                    res, \n                    dfs(False, l + 1, r) + total - stones[l],\n                    dfs(False, l, r - 1) + total - stones[r]\n                )\n                has_cacheA[l][r] = True\n                cacheA[l][r] = res\n\n            else:\n                res = min(\n                    res,\n                    dfs(True, l + 1, r) - (total - stones[l]),\n                    dfs(True, l, r - 1) - (total - stones[r])\n                )\n                has_cacheB[l][r] = True\n                cacheB[l][r] = res\n\n            return res\n\n        return dfs(True, 0, n - 1)\n        \n```
['Python3']