C++| Topdown Tree Traversal + Memoization | Lots of explanation.
The result of the each turns follows a decision tree:\n\n each turn\'s result is the value of piles[left] or piles[right]\n left, right value follows a patterns
The result of the each turns follows a decision tree:\n\n* each turn\'s result is the value of piles[left] or piles[right]\n* left, right value follows a patterns: if a left stone is taken, the next left is left+1; if a right stone is taken, the next right is right-1\n* each turn is called recursively:\n```\nscore = player\'s score in current turn   + recursivefunction  (data set, next left, next right, cache, prefixSum)\n```\nIllustration of decision tree\n![image](https://assets.leetcode.com/users/images/3f5b3b06-d4d9-41cd-a8ca-5f6e1fea8f57_1647498085.9716723.png)\n\n* player\'s score in current turn is calculate by `prefixSum`  - that way we don\'t have to run for loop to calculate score.\n```\nfor example: for data set { 5,2,3,1 }\nThe value {5,2,3}, if a player takes 1 is: 5+ 2 + 3 = 10 = (5+2+3+1) - 1 =prefixSum[4] - prefixSum[3]\nThe value {2,3,1} if a player takes 5 is: 2+3+1 = 6 = (5+2+3+1) - 5 = prefixSum[4] - prefixSum[0]\nprefixSum[0] = 0\nprefixSum[1] = 5\nprefixSum[2] = 5+2=7\nprefixSum[3] = 5+2+3=10\nprefixSum[4] = 5+2+3+1=11      // note that prefix sum has size + 1\n``` \n\n* the player turn is identified by even/odd values: Zero turn: game starts; Odd turn: Alice plays, Even turn: Bob plays.\n* the result of each turns is the different = Alice score - Bob score. Thus when Alice plays, score += AliceScore; and when Bob plays, score -=BobScore\n* the final score is returned to original call of recursive funtion , turn 0. \n\nMemoization is implemented: an array cache[left][right] saved a value for later retrieval. It helps pruning the tree: the branch that are repeated will not be visited again; instead, its value is returned from saved cache. Cache is initialized to INT_MAX (must use #include #include <bits/stdc++.h>)\n\nTraversing the tree is topdown. Top = root of tree = turn index = 0 (left =0, right = size of piles -1)\n\nTo further optimizing the run-time, pass by reference is used in recursive function; it saves time from making copy of piles, cache etc while invoking functions.\n\nThe code could be further optimized by not declaring local variables, but I used them anyway, for better code reading. \n\n```\n// Tree traversing + memoization\nclass Solution {\npublic:\n    \n    int turnScore (vector<int>&piles, int left, int right, int turn, vector<vector<int>>&cache, vector<int>&prefixSum){\n        // cout<<"turn: "<<turn<<" (left,right="<<left<<","<<right<<")"<<endl;\n        int sum = 0, a=0,b=0;\n        // base case\n        if (left>right) return 0;           // must have because if not, for case left=0, right=-1, if(cache[left][right]) return segfault \n        // if (left== right)                // no neccessary since it is included in recursive case      \n        // memoization - return via cache\n        if (cache[left][right] !=INT_MAX ){\n            // cout<<"return cache["<<left<<"]["<<right<<"]="<<cache[left][right]<<endl;\n            return cache[left][right];\n        }\n        // starting, no one play yet.\n        if (turn == 0){                                                             \n            int sum = 0;\n            int a = turnScore(piles, left, right-1, turn+1, cache, prefixSum);\n            int b = turnScore(piles, left+1, right, turn+1, cache, prefixSum);            \n            int c = max(a,b);\n            // cout<<"sum:"<<sum<<" a:"<<a<<" b:"<<b<<" c:"<<c<<endl;\n            return c;\n        }  \n        \n        // both players scores when left <= right \n        // input left, right indicates the range of remaining cards after the player removes a card\n        // score = sum (left -> right) + turnResult (leftNext, rightNext, nextTurn)\n        else if ((left <= right) && (turn %2 == 0)){                                 // Bob plays      \n            sum = prefixSum[right+1]-prefixSum[left];\n            \n            a = turnScore(piles, left+1, right, turn+1, cache, prefixSum);  \n            b = turnScore(piles, left, right-1, turn+1, cache, prefixSum);                                                       \n            cache[left][right] = -sum + max(a,b);                        // max(a,b) is the score of the next player, Alice \n            // cout<<"return value recursively"<<endl;\n            // cout<<"turn: "<<turn<<" (left,right="<<left<<","<<right<<")"<<endl;\n            // cout<<"sum:"<<sum<<endl;\n            // cout <<"total "<< cache[left][right] <<endl;\n            return cache[left][right];\n        } \n        else if ((left <= right) && (turn %2 != 0)){                                 // Alice plays\n            sum = prefixSum[right+1]-prefixSum[left];\n            a = turnScore(piles, left+1, right, turn+1, cache, prefixSum);  \n            b = turnScore(piles, left, right-1, turn+1, cache, prefixSum);                                                   \n            cache[left][right] = sum + min(a,b);                                // min(a,b) is the score of the next player, Bob  \n            // cout<<"return value recursively"<<endl;\n            // cout<<"turn: "<<turn<<" (left,right="<<left<<","<<right<<")"<<endl;\n            // cout<<"sum:"<<sum<<endl;\n            // cout <<"total "<< cache[left][right] <<endl;\n            return cache[left][right];\n        }\n        else\n            return 0;\n    }\n\n    int stoneGameVII(vector<int> &piles)\n    {\n        int left = 0;\n        int right = piles.size()-1;\n        int n = piles.size();\n        int turn = 0;\n        vector<vector<int>> cache (n,vector<int>(n, INT_MAX));\n        vector<int> prefixSum(n + 1);\n        for (int i = 0; i < n; i++) {\n            prefixSum[i + 1] = prefixSum[i] + piles[i];\n        }\n        int score = turnScore(piles, left, right, turn, cache, prefixSum);        // total score at top of tree\n                                                                       // total score = Alice score - Bob score\n        return score;\n    }\n};\n```
[]