C++ no prefix sum O(n^2)
We look at turns as both Alice and Bob choosing a stone each with Alice choosing first.\n\nThere are 4 options\n Alice leftmost Bob rightmost -> lr\n Alice left
We look at turns as both Alice and Bob choosing a stone each with Alice choosing first.\n\nThere are 4 options\n* Alice leftmost Bob rightmost -> lr\n* Alice leftmost then Bob leftmost from remaining -> ll\n* Alice rightmost then Bob leftmost -> rl\n* Alice leftmost then Bob rightmost -> lr\n\nWe calculate for all 4 options, the difference in scores.\n\nThen as we know, Alice has the first turn, so she will try to minimise the difference.\n\nlet\'s say lr = 6, rl = 7, ll = 5, rr = 10\n\nNow you can see, if Alice choose the left stone, Bob will choose the next left stone to minimise diff.\nif Alice choose rightmost, bob will choose the leftmost\n\nfor alice, best case option is she choose right and then Bob will for sure choose leftmost.\n\n\n```class Solution {\npublic:\n    vector<vector<int>> dp;\n    int minDiff(vector<int> &stones, int left, int right) {\n        if( left == right )\n            return 0;\n        if( right < left )\n            return 0;\n        \n        if( dp[left][right] != INT_MAX)\n            return dp[left][right];\n        int ll = stones[left + 1] + minDiff(stones, left + 2, right );\n        int rr = stones[right - 1] + minDiff(stones, left, right - 2 );\n        int minlr = minDiff( stones, left + 1, right - 1 );\n        int lr = stones[right] + minlr;\n        int rl = stones[left] + minlr;\n        \n        if( min(ll,lr)  < min(rr,rl) )\n            dp[left][right] = min(rr, rl);\n        else\n            dp[left][right] = min(ll, lr);\n        \n        return dp[left][right];\n    }\n    int stoneGameVII(vector<int>& stones) {\n        int n = stones.size();\n        dp = vector<vector<int>>(n, vector<int>(n,INT_MAX));\n        return minDiff(stones, 0, stones.size() - 1);\n    }\n};\n```
[]