Python | Recursive DP | Min Max | Two Pointer | with Explaination
This is an application of Min/Max algorithm where one of competitor alice, tries to maximize the difference, while other bob tries to minimize it.\n\nSo the DP 
This is an application of Min/Max algorithm where one of competitor `alice`, tries to maximize the difference, while other `bob` tries to minimize it.\n\nSo the DP or recursive solution you write, depending on, which players turn it is, you maximize or minimize the return value.\n\n## Step 1: Identifying sub-problem:\nWe will be using two pointers left `l` and right `r` to identify sub-array, thus sub-problem to solve. Solving sub-problem we will compute the solution to the whole `(0, N]`.\n\n## Step 2: Identifying which players turn it is:\nWe could have passed `bool` valirable around to identify which players turn it is. \nThis is redundant as we can deduce it from `l` and `r` values itself, i.e after each turn either `l -> l + 1` or `r -> r - 1`. Thus after each turn, `l` and `r` comes closer to each other by `1-step`. Depending on how many stones are remaining, i.e `remaining = (N - (r - l))`,  we can tell if remaining is odd => `alice`\'s else `bob`\'s turn.\n\nThus to know which players turn it is:\n```python\nis_alice = (N - (r - l)) & 1\n```\n\n## Step 3: Computing difference in players score:\n\nTo compute answer, we need to take difference in total scores b/w two players accumulated over each turn.\n\nLooks complecated, but it can be reduced to sum of stone values picked by loosing player, i.e `Bob`. Here is the proof for the same.\n\nFor example:\n```\nConsider you have 4 stones: [a, b, c, d] with sum S = (a + b + c + d)\nLet Stone choices be:\nAlice:  a, c\nBob :   b, d\n\n|  Turn |         1        | 2 |\n|:-----:|:----------------:|:-:|\n| Alice |    a1 = S - a    | d |\n|  Bob  |    b1 = a1 - b   | 0 |\n|  Diff |    b = a1 - b1   | d |\n```\n**Thus Final result = sum of diffs = b + d == sum of `Bobs` stone values**\n\n> ### All we need to do is add the values of stones picked by `bob` which will be diffs in two player scores.\n\n---\n\n# FInal solution looks like this:\n- Time: O(N), because of caching sub-problem solution. _Correct me if I am wrong_\n- Space: O(N * N), because of `lru_cache` saving results for all `nC2` pairs of `(l, r)`.\n\n```python\nclass Solution:\n    def stoneGameVII(self, stones: List[int]) -> int:\n        N = len(stones)\n\n        @lru_cache(maxsize=2000)\n        def dfs(l: int, r: int) -> int:\n            is_alice = (N - r + l) & 1\n            if l == r:\n                return (1 - is_alice) * stones[l]\n            if is_alice:\n                return max(dfs(l + 1, r), dfs(l, r - 1))\n            return min(stones[l] + dfs(l + 1, r), stones[r] + dfs(l, r - 1))\n\n        return dfs(0, N - 1)\n```\n\n**Runtime: 4676 ms\nMemory Usage: 21 MB**
['Two Pointers', 'Dynamic Programming', 'Recursion', 'Python']