Top Down, C++ | Simple
Calculate the difference directly by subtracting the optimal value chosen by the other player. Store the redundant states in a table.\n\nclass Solution {\npubli
Calculate the difference directly by subtracting the optimal value chosen by the other player. Store the redundant states in a table.\n```\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    int stoneGameVII(vector<int>& stones) {\n        dp.resize(stones.size(),vector<int>(stones.size(),-1));\n        int total=0;\n        for(int num:stones) total+=num;\n        return stoneGameRec(0,stones.size()-1,total,stones);\n    }\n    int stoneGameRec(int i, int j, int total,vector<int>& stones) {\n        if(i>=j) return 0;\n        if(dp[i][j]!=-1) return dp[i][j];\n        int op1=(total-stones[i]) - stoneGameRec(i+1,j,total-stones[i],stones);\n        int op2=(total-stones[j]) - stoneGameRec(i,j-1,total-stones[j],stones);\n        return dp[i][j]=max(op1,op2);\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']