Python: Explained DP both Memoization(Top-Down) and Tabulation(Bottom-Up)
This problem cannot be solved using Greedy Approach as both Alice and Bob needs to play optimally and greedy always does not guarantee an optimal solution.\n\nS
This problem cannot be solved using Greedy Approach as both Alice and Bob needs to play optimally and greedy always does not guarantee an optimal solution.\n\nSo, the only possible way to solve this is to enumerate all the possibilities Alice/Bob has in each turn. \nE.g.: stones = [5,3,1,4,2]\nAlice chooses both 5 and 2 parallely and removes them, when alice removes 5 bob has 2 options to remove 3 and 2 and bob tries both... but when alice removes 2 bob has two options 5 and 4 and bob will also try both and see which one is a better option... and so on...\n\nHere, each stone has two possibilites whether to be removed or not. Hence, total possibilites = O(2 ^ n) where n is the number of stones.\n\nThus by simple recurssion we will have Time = O(2^n) to go through all the possibilities and Space  = O(n) owing to the depth of the binary tree (recursion stack).\n\nRecursion Tree Code: Sure TLE. ........ Time = O(2^n) and Space = O(n).\n```\nclass Solution:\n    def stoneGameVII(self, stones: List[int]) -> int:\n        n = len(stones)\n        \n        prefix = [0]\n        for i in stones:\n            prefix.append(prefix[-1]+i)\n        \n        def solve(left, right):\n            if left == right:\n                return 0\n            \n            leftScore = prefix[right+1] - prefix[left+1] - solve(left+1,right)\n            rightScore = prefix[right] - prefix[left] - solve(left,right-1)\n            return max(leftScore,rightScore)\n        \n        return solve(0,n-1)\n```\n\nif stones = [5,3,1,4,2], then prefix sum array = [0,5,8,9,13,15].... An additional zero is just added for better indexing.\n\nHere prefix sum array is needed so that we do not need to calculate sum every time, \nlike if alice removes 5 we can calulate the sum of rest of array as total sum of the array - sum upto the element 5 = prefix[n] - prefix[1] and so on.\n\nNow, why will the recursive equation hold?\n``` leftScore = prefix[right+1] - prefix[left+1] - solve(left+1,right) ```\nThis depicts a player\'s turn (may it be alice or bob), so if the player is removing the left stone we calulate the sum of stones values excluding the left most stone and ask the other player to play (solve(left+1,right)) with stones excluding  the left most one. Then we get the difference of the scores of both the players.\n\nSimilar is the case when we exclude the rightmost stone and include the leftmost stone.\n\nIn this way we keep checking all the possibilities.\nAnd the base case is left == right as then we have only one element, so if we remove it the score/sum is zero and the game ends.\n\nI hope this recursive idea makes sense. \n\nNow, coming to the time complexity issue. T = O(2^n) will definitely give a TLE. \nCan we memoize? - Yes, due to overlapping subproblems.\nE.g.:  stones = [5,1,3,4,2], one case of overlapping sub problems is [1,3,4] will be solved for both alice and bob. And there are many other overlaps.\n\nIf we memoize we will just have N^2 possible recurssion states, as both left and right has \'n\' possible values and the travel parallely. Hence Time = O(n^2) Space = O(n^2) owing to DP array.\n\nRecurssion + Memoization (Top - Down DP): Accepted ........... Time = O(n^2) Space = O(n^2)\n```\nclass Solution:\n    def stoneGameVII(self, stones: List[int]) -> int:\n        n = len(stones)\n        \n        prefix = [0]\n        for i in stones:\n            prefix.append(prefix[-1]+i)\n        \n        dp = [[-1]*n for _ in range(n)]\n        \n        def solve(left, right):\n            if left == right:\n                return 0\n            \n            if dp[left][right]!=-1:\n                return dp[left][right]\n            \n            leftScore = prefix[right+1] - prefix[left+1] - solve(left+1,right)\n            rightScore = prefix[right] - prefix[left] - solve(left,right-1)\n            \n            dp[left][right] = max(leftScore,rightScore)\n            return dp[left][right]\n        \n        return solve(0,n-1)\n```\n\nAnd as we know, every memoized DP can be converted to Tabulation(Bottom-Up DP) by just converting the recurssion to Iteration. \n\nIn Top-Down DP (memoization), we traverse from the larger problem recursively to the smaller problem and we keep throwing the answer to the top/parent level.\n\nBut In Bottom-Up DP(Tabulation), we move from smaller problem to the larger problem iteratively(additively).\nThe main concept remains the same for both.\n\nBottom- Up DP:  Accepted ........... Time = O(n^2) Space = O(n^2)\n```\nclass Solution:\n    def stoneGameVII(self, stones: List[int]) -> int:\n        n = len(stones)\n        \n        prefix = [0]\n        for i in stones:\n            prefix.append(prefix[-1]+i)\n        \n        dp = [[0]*n for _ in range(n)]\n        \n        for left in range(n-1,-1,-1):\n            for right in range(n):\n                if left == right:\n                    dp[left][right] = 0\n                else:\n                    leftScore, rightScore = 0, 0\n                    if left+1 < n:\n                        leftScore = prefix[right+1] - prefix[left+1] - dp[left+1][right]\n                    if right - 1 >= 0:\n                        rightScore = prefix[right] - prefix[left] - dp[left][right-1]\n                    dp[left][right] = max(leftScore,rightScore) \n        return dp[0][n-1]\n        \n```\n\nHope it helps!
['Dynamic Programming', 'Memoization', 'Python']