C++, Top-Down DP, O(n*n), Basic logic of game solving
Logic used - \n1. Every time a player has to make a turn, he/she has 2 choices i.e whether to start from leftmost element or the rightmost element.\n2. Alice is
Logic used - \n1. Every time a player has to make a turn, he/she has 2 choices i.e whether to start from leftmost element or the rightmost element.\n2. Alice is trying to increase the difference so his score at every step will always be to "add" to the overall difference, so take the MAX of the 2 next states, choosing leftmost or choosing rightmost.\n3. Bob is trying to decrease the differenec so his score at every step will always be to "reduce" the overall difference, so take the MIN of the 2 next states, choosing leftmost or choosing rightmost.\n4. The total number of states are ```number of possible subarrays*2 ``` . Multiplies by 2 because every [start,end] can come for each player.\n\nprefix array is used to get the score[start-end] in O(1) time;\nturn = true means that alice is playing\nturn = false means that bob is playing\n\nPS : if you use ```vector<vector<vector<int>>> dp```, you will get TLE, that is way I used arrays.\n\n```\nclass Solution {\npublic:\n    int dp[1001][1001][2] = {};\n    int prefix[1001];\n    int fn(int s,int e,bool turn){\n        if(s==e) return 0;\n        \n        int curr = 0;\n        if(!turn) curr = 1;\n        if(dp[s][e][curr]!=0) return dp[s][e][curr];\n        \n        if(turn){\n            int first = fn(s+1,e,!turn) + prefix[e]-prefix[s];\n            int second = fn(s,e-1,!turn) + prefix[e-1]-((s-1>=0) ? prefix[s-1] : 0);\n            dp[s][e][0] = max(first,second);\n            return dp[s][e][0];\n        }\n        else{\n            int first = fn(s+1,e,!turn) - (prefix[e]-prefix[s]);\n            int second = fn(s,e-1,!turn) - (prefix[e-1]-((s-1>=0) ? prefix[s-1] : 0));\n            dp[s][e][1] = min(first,second);\n            return dp[s][e][1];\n        }\n    }\n    int stoneGameVII(vector<int>& stones) {\n        int n = stones.size();\n        prefix[0] = stones[0];\n        for(int i=1;i<n;i++) prefix[i] = prefix[i-1] + stones[i];\n        return fn(0,n-1,true);\n    } \n};\n```
['Dynamic Programming', 'C']