Straight forward DP solution | Memoizaton | c++ | O(n*n)
\nint pre[1005];\nint getsum(int l,int r){\n    if(l > r)\n        return 0;\n    return pre[r] - (l>0?pre[l-1]:0);\n}\n\nint cache[1005][1005][2];\nint dp(int 
```\nint pre[1005];\nint getsum(int l,int r){\n    if(l > r)\n        return 0;\n    return pre[r] - (l>0?pre[l-1]:0);\n}\n\nint cache[1005][1005][2];\nint dp(int l,int r,int f)\n{\n    if(l > r)\n        return 0;\n    int &ans = cache[l][r][f];\n    if(ans != -1)\n        return ans;\n    int lsum = getsum(l,r-1) , rsum = getsum(l+1,r);\n    if(f==0)\n        ans = max(rsum + dp(l+1,r,f^1) , lsum + dp(l,r-1,f^1));\n    else\n        ans = min(-rsum + dp(l+1,r,f^1),-lsum + dp(l,r-1,f^1));\n    return ans;\n}\nclass Solution {\npublic:\n    int stoneGameVII(vector<int>& stones) {\n        int n = stones.size();\n        \n        // initialize cache array\n        for(int i =0;i < n; ++i){\n            pre[i] = 0;\n            for(int j =0;j < n; ++j)\n                cache[i][j][0] = cache[i][j][1] = -1;\n        }\n        \n        // build prefix sum array\n        for(int i = 0;i < n; ++i){\n            if(i > 0)\n                pre[i] = pre[i-1];\n            pre[i] += stones[i];\n        }\n        return dp(0,n-1,0);\n        \n    }\n};\n```
['Memoization']