✅ Stone Game VII | Dynamic Programming | Explanation
Intuition:\n\n1. Both Alice and Bob is playing optimally, so we need to consider the situation for one person.\n2. Let us say we are considering Alice case, if 
**Intuition:**\n```\n1. Both Alice and Bob is playing optimally, so we need to consider the situation for one person.\n2. Let us say we are considering Alice case, if Alice starts first then she has two options:\n* She can remove the first stone in the current stones.\n* She can remove the last stone in the current stones.\n\nIf Alice removed first stone,\nthen Bob can select from remaining stone but not the removed stone.\n\nLet us consider a simple case:\nStones: [1,2,3,4]\nAlice starts first:\nnow she can either remove 1 or 4\nif she removed 1 then Bob will have these options for his turn [2,3,4]\nif she removed 4 then Bob will have these options for his turn [1,2,3]\n\nNote: Bob and Alice both are playing optimally so Alice and Bob both want to obtain maximum points, or in simple term Alice want the difference between their scores i.e. AliceScore-BobScore as maximum and Bob wants the difference as minimum.\n\nIn below code I am considering the situation of Alice,\nSo she wants to maximize the difference between their scores,\nShe will try to see both possibilities and pick the possibility which is maximising the difference.\n\nIf Alice choose stone at index i,(i.e, taking stones from Front)\nthen the Points Alice will get is = Total Sum Of Stones Values - Stone[i];\n\nIf she choose stone at index j,(i.e, taking stones from Back)\nthen the Points Alice will get is = Total Sum Of Stones Values - Stone[j];\n\nAnd at every step Bob can form his score from  min(Total Sum Of Stone Values-Stone[i],Total Sum Of Stones Values - Stone[j]);\n\nPlease see the below solution for more clarity.\n```\n\n```\nNote:\n1) Alice is always starting first according to question.\n2) We need to consider only that possibility which is yielding the best results for Alice i.e, maximising the difference between their scores.\n```\n**C++:**\n```\nclass Solution {\npublic:\n    int dp[1002][1002];\n\tint getMaxDiff(vector<int> &v,int i,int j,int sum)\n    {\n        if(i>=j)\n            return 0;\n        if(sum<0)\n            return 0;\n        if(dp[i][j]!=-1)\n            return dp[i][j];\n        return dp[i][j]=max(sum-v[i]-getMaxDiff(v,i+1,j,sum-v[i]),sum-v[j]-getMaxDiff(v,i,j-1,sum-v[j]));\n        \n    }\n    int stoneGameVII(vector<int>& stones) \n    {\n        memset(dp,-1,sizeof(dp));\n        int sum=0;\n        for(auto i:stones)\n            sum+=i;\n        return getMaxDiff(stones,0,stones.size()-1,sum); \n        \n    }\n};\n```
['C']