[Python3] Easy code with explanation - DP
The subproblem for the DP solution is that,\nFor n = 1, Alice or Bob picks the stone and nobody gets any score.\nFor n = 2, the person picks first stone and the
The subproblem for the DP solution is that,\nFor n = 1, Alice or Bob picks the stone and nobody gets any score.\nFor n = 2, the person picks first stone and the score equals second stone or vice versa.\nso on....\n\nNow, that we have the subproblem how do we fill the DP table and fill it with what?\nI thought of 3 choice for entries into the DP table - Alice\'s score, Bob\'s score or **difference of their scores**.\nIt gets messy for the rest so I chose difference of their scores. After zeroing on that, what should be the size of the table?\nEach table entry dp[i][j] signifies the difference in scores between the ith stone and jth stone.\nNow that we know what i and j mean its obvious that we have to find the difference of scores between the 0th stone and nth stone.\n\nOkay, next question that arises is, how do we fill the table entry when its Bob\'s turn and when its Alice\'s turn?\nNote that: the difference of scores is : (sum of scores obtained by Alice) - (sum of scores obtained by Bob)\nWhen its **Bob\'s turn**, his target is to minimize the difference:\n**dp[i][j]  = min(dp[i][j-1] - (score after removing jth stone), dp[i+1][j] - (score after removing ith stone))**\n\ndp[i][j] -> Difference in score between ith and jth stone\ndp[i][j-1] -> Difference in score between ith and j-1 th stone\ndp[i+1][j] -> Difference in score between i+1 th and j th stone\n\nThe intuition is to make the negative part larger to minimize the difference.\n\nWhen its **Alice\'s turn**, her target is to maximize the difference:\n**dp[i][j]  = min(dp[i][j-1] + (score after removing jth stone), dp[i+1][j] + (score after removing ith stone))**\n\ndp[i][j] -> Difference in score between ith and jth stone\ndp[i][j-1] -> Difference in score between ith and j-1 th stone\ndp[i+1][j] -> Difference in score between i+1 th and j th stone\n\nThe intuition is to make the positive part larger to maximize the difference.\n\nIf even number of stones were removed from the array then the upcoming turn is Alice\'s and similary for Bob odd number of stones must be removed.\n\nThe direction left to right and bottom to top.\n\nExample of DP table for : 5,3,1,4,2\n\n![image](https://assets.leetcode.com/users/images/16f2a58d-61ed-49bf-82a0-a6e0965c1d51_1608071659.1524374.png)\n\nRunning time: O(n^2)\nMemory : O(n^2)\n\nThis question is similar to: https://leetcode.com/problems/stone-game-vi/\n\n```\nclass Solution:\n    def stoneGameVII(self, stones: List[int]) -> int:\n        dp = [[0 for _ in range(len(stones))] for _ in range(len(stones))]     # dp table n x n\n        run_sum = [0]                            # running sum -> sum [i..j] = run_sum[j] - run_sum[i]\n        s = 0\n        \n\t\t## Calculation of running sum\n        for i in stones:\n            s += i\n            run_sum.append(s)\n\t\t\n        n = len(stones) \n        \n        for k in range(1, n):               # no. of stones left\n            for i in range(0, n - k):   # from each starting point\n                remove_i_stone = (run_sum[i+k+1] - run_sum[i+1])    # score after removing i th stone\n                remove_j_stone = (run_sum[i+k] - run_sum[i])             # score after removing j th stone\n                \n                if (n-(k+1))%2 == 0:        # alice\'s move \n                    dp[i][i+k] = max(remove_i_stone + dp[i+1][i+k],\n                                    remove_j_stone + dp[i][i+k-1])\n                else:                       # bob\'s move\n                    dp[i][i+k] = min(-remove_i_stone + dp[i+1][i+k],\n                                    - remove_j_stone + dp[i][i+k-1])\n                    \n        return dp[0][n - 1]\n```
['Dynamic Programming', 'Memoization', 'Python', 'Python3']