C++ DP with explanation (easy)
\n\t\nf(i, j, stones) : denotes the maximum lead that the current player can take while playing in the subarray stones[i...j] /  or how ahead can the current pl
\n\t\n**f(i, j, stones) : denotes the maximum lead that the current player can take while playing in the subarray stones[i...j] /  or how ahead can the current player reach from the opponent given that both play optimally**\n\t\nAt any instant, the player whose turn it is currently, will try and take maximum lead (means he will try to make the difference in the scores (or how much ahead he is of the opponent will be maximized))\n\t\n\nas soon as we pick a stone from an end , lets say we pick up the stone at index i, so we immediattely take a lead of sum(i+1, j) (means we are now sum(i +1, j) ahead of the first guy)\nnow the second guy will take a lead of f(i + 1, j) \nso \n**the overall lead that we took in this case is sum(i + 1, j) - f(i+1, j)**\n\nsimilarly if i pick up the stone at index j (the right end) we immediattely take a lead of sum(i, j-1) and now it\'s the opponents turn\n**so he will take a lead of f(i, j-1), so again the lead in this case is sum(i, j-1) - f(i, j-1)**\n\n**all we have to do is, go for the maximum of the above two cases**\n\n```\nclass Solution {\npublic:\n\tvector<int> prefixSum;\n\tvector<vector<int>> dp;\n\tint sum(int i, int j) {\n\n\t\treturn (j >= 0 ? prefixSum[j] : 0) - (i >= 1 ? prefixSum[i - 1] : 0 );\n\t}\n\n\tint f(int i, int j, vector<int> &stones) {\n\n\t\tif (i >= j) return 0;\n\t\tif (dp[i][j] != -1) return dp[i][j];\n\n\t\treturn dp[i][j] = max(sum(i + 1, j) - f(i + 1, j, stones), sum(i, j - 1) - f(i, j - 1, stones));\n\t}\n\tint stoneGameVII(vector<int>& stones) {\n\t\tint n = stones.size();\n\t\tprefixSum.resize(n, 0);\n\t\tdp.resize(n, vector<int> (n, -1));\n\t\tint s = 0;\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\ts += stones[i];\n\t\t\tprefixSum[i] = s;\n\t\t}\n\n\t\treturn f(0, n - 1, stones);\n\t}\n};\n```
[]