C++ || Top down || Bottom up || Detailed Explanation || Beginner Friendly
Code:\n\nTop-Down:\n\n\nclass Solution\n{\npublic:\n    vector<vector<int>> memo;\n    vector<int> preSum;\n    int getSum(int i, int j)\n    {\n        return 
**Code:**\n\n**Top-Down:**\n\n```\nclass Solution\n{\npublic:\n    vector<vector<int>> memo;\n    vector<int> preSum;\n    int getSum(int i, int j)\n    {\n        return preSum[j + 1] - preSum[i];\n    }\n    int dp(int i, int j)\n    {\n        if (i == j)\n            return 0; // only 1 stone, score = 0 -> difference = 0 as well\n        if (memo[i][j] != INT_MAX)\n            return memo[i][j];\n        int s1 = getSum(i + 1, j); // choose ith stone\n        int s2 = getSum(i, j - 1); // choose jth stone\n        int ans = max(s1 - dp(i + 1, j), s2 - dp(i, j - 1));\n        return memo[i][j] = ans;\n    }\n    int stoneGameVII(vector<int> &stones)\n    {\n        int n = stones.size();\n        memo.assign(n, vector<int>(n, INT_MAX));\n        preSum.assign(n + 1, 0);\n        for (int i = 0; i < n; i++)\n            preSum[i + 1] = preSum[i] + stones[i];\n        return dp(0, n - 1);\n    }\n};\n```\n\n**Bottom-Up:**\n\n```\nclass Solution\n{\npublic:\n    vector<int> preSum;\n    int getSum(int left, int right)\n    {\n        return preSum[right + 1] - preSum[left];\n    }\n    int stoneGameVII(vector<int> &stones)\n    {\n        int n = stones.size();\n        preSum.assign(n + 1, 0);\n        for (int i = 0; i < n; i++)\n            preSum[i + 1] = preSum[i] + stones[i];\n\n        vector<vector<int>> dp(n, vector<int>(n, 0));\n        for (int i = n - 1; i >= 0; i--)\n        {\n            for (int j = i + 1; j < n; j++)\n            {\n                int s1 = getSum(i + 1, j); // choose ith stone\n                int s2 = getSum(i, j - 1); // choose jth stone\n                dp[i][j] = max(s1 - dp[i + 1][j], s2 - dp[i][j - 1]);\n            }\n        }\n        return dp[0][n - 1];\n    }\n};\n```\n\n**Method:**\n* alice is trying to maximize the difference\n    * in otherwords, she is trying to maximize her score\n* bob is trying to minimize the difference\n    * in otherwords, he is trying to maximize his score\n* So, in this problem at any given point both alice and bob are trying to get the maximum score possible\n* Let\'s say there are n=5 stones\n    * now, alice starts first\n    * so for the whole process\n    * ```alice gain = a1 + a3 + a5```\n    * ```bob gain = b2 + b4```\n        * where\n        * ```a1 = sum obtained by alice in the 1st round```\n        * ```b2 = sum obtained by bob in the 2nd round```\n    * Now,\n    * ```diff = (a1+a3+a5)-(b2+b4) for stones[1,5]```\n    * Note that,\n    * ```a1>b2>a3>b4>a5```\n    * why?\n        * because each stone[i]>=1\n        * so if,\n        * ```a1 = stone[i]+....+stone[j]```\n        * ```b2 = stone[i+1]+....stone[j] or stone[i]+...stone[j-1]```\n        * so it is clear that b2<a1\n    * getting back at diff\n    * we can rewrite it as\n    * ```diff = a1-(b2+b4 -a3-a5)```\n        * i.e a1 - (diff for stones[2,5])\n        * again,\n        * ```diff = a1-(b2-(a3+a5 - b4))```\n        * i.e  = a1-(b2- (diff for stones[3,5]))\n        * so,\n        * ```diff = a1-(b2-(a3-(b4-a5)))```\n* in general we can say that,\n* **```diff = current_round_gain - (sub_problem_diff)```**\n* Also, Note that,\n* **we don\'t have to keep track of turns**\n* why?\n    * ```Alice goal: maximize the final diff```\n    * ```Bob goal : minimuze the final diff```\n    * From this\n    * **```final diff = a1-(b2-(a3-(b4-a5))) = a1-(subproblem)```**\n    * we can see that\n    * Alice wants to\n        * maximize a1-subproblem,\n        * so Alice wants to maximize a3-subproblem due to the double negation.\n    * The same goes for Bob.\n        * Bob wants to minimize a1-subproblem = final_diff,\n        * so Bob wants to maximize b2-subproblem = diff at bob turn,\n        * then maximize b4-subproblem due to double negation.\n        * (i.e we can say bob will try to maximize the diff at his turn so that the final diff is as min as possible)\n* So,\n* we can conclude that\n* **goal of bob = minimize the final diff**\n* **goal of alice = maximize the final diff**\n* **but at each round both will try to maximize the current diff**\n\n\n**Implementation:**\n\n* ```dp[i][j] = alex_sum - bob_sum = difference```\n* we create a prefixSum array to store the prefixSum\n    * ```prefixSum(i) = sum of all the elements from 0 to i(i not included)```\n    * ```prefixSum(j) = sum of all the elements from 0 to j(j not included)```\n* so if we want to find sum from index i to j\n    * ```sum = prefixSum(j+1)-prefixSum(i)```\n* if alice chooses ith pile:\n    * ```diff = sum(i-1,j) - dp[i+1][j]```\n* if alice chooses jth pile:\n    * ```diff = sum(i-1,j) - dp[i+1][j]```\n* **ans = dp[0][n-1]**\n
['Dynamic Programming', 'Memoization', 'C', 'C++']