C++ memoization code with proper explanation
\n\nclass Solution {\npublic:\n    int dp[1001][1001];\n    int solve(vector<int>& stones, int i, int j, int sum){\n        if(i>=j){\n            return 0;\n  
\n```\nclass Solution {\npublic:\n    int dp[1001][1001];\n    int solve(vector<int>& stones, int i, int j, int sum){\n        if(i>=j){\n            return 0;\n        }\n        if(sum<=0){\n            return 0;\n        }\n        if(dp[i][j]!=-1){\n            return dp[i][j];\n        }\n        \n        // both the player have two options either they can choose the first element\n        // or they can choose the last element\n        // they will choose that particular element which will give them the maximum                profit\n        // as player A wants to maximize its profit\n        // and player B wants to minimize the difference between them\n        // hence both will choose the maximum value only\n        int choose_front = sum-stones[i]-solve(stones,i+1,j,sum-stones[i]);\n        int choose_back = sum-stones[j]-solve(stones,i,j-1,sum-stones[j]);\n        \n        int profit = max(choose_front,choose_back);\n        return dp[i][j] = profit;\n    }\n    int stoneGameVII(vector<int>& stones) {\n        int n = stones.size();\n        int sum = 0;\n        for(int i=0;i<n;i++){\n            sum+=stones[i];\n        }\n        memset(dp,-1,sizeof(dp));\n        // same as stone game-II, III \n        // here value is the difference between profit of A and profit of B\n        int value =  solve(stones,0,n-1,sum);\n        return value;\n    }\n};\n```\n\n---------------------------------------------------------------------------------------------------------------\nfor any state[i,j] ,\nthere are two things either i can choose front element or back element.\n\nlet us take example for front -> int choose_front = sum-stones[i]-solve(stones,i+1,j,sum-stones[i]); \n1.  sum-stones[i] => this is the profit that current player make if he choose the front element\n2.  solve(stones,i+1,j,sum-stones[i]) => the value of this function represent the optimal profit that the opponent can make\nhence  equation [ int choose_front = sum-stones[i]-solve(stones,i+1,j,sum-stones[i]) ] represents the difference between current player\'s profit and opponent\'s profit.\n* same for choose_back case.\n\nAs question required, difference in Alice and Bob\'s score if they both play optimally. So by maximum profit for current state[i,j] we mean, the maximum difference between current player\'s profit and opponent\'s profit (that can come from either choosing back_element or the front_element).\n**Time complexity -> O(n*n)**\n\n---------------------------------------------------------------------------------------------------------------\n\n**Try these questions also**\n*logic is 80% same*\n[1140. Stone Game II](https://leetcode.com/problems/stone-game-ii/discuss/1247693/C%2B%2B-memoization-with-proper-explanation)\n[1406. Stone Game III](https://leetcode.com/problems/stone-game-iii/)\n\n**Please upvote 0\'_\'0**
['Memoization', 'C', 'C++']