<p>Alice and Bob continue their games with piles of stones. There are a number of piles <strong>arranged in a row</strong>, and each pile has a positive integer number of stones <code>piles[i]</code>. The objective of the game is to end with the most stones.</p>

<p>Alice and Bob take turns, with Alice starting first.</p>

<p>On each player&#39;s turn, that player can take <strong>all the stones</strong> in the <strong>first</strong> <code>X</code> remaining piles, where <code>1 &lt;= X &lt;= 2M</code>. Then, we set <code>M = max(M, X)</code>. Initially, M = 1.</p>

<p>The game continues until all the stones have been taken.</p>

<p>Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">piles = [2,7,9,4,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">10</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get <code>2 + 4 + 4 = 10</code> stones in total.</li>
	<li>If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get <code>2 + 7 = 9</code> stones in total.</li>
</ul>

<p>So we return 10 since it&#39;s larger.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">piles = [1,2,3,4,5,100]</span></p>

<p><strong>Output:</strong> <span class="example-io">104</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= piles.length &lt;= 100</code></li>
	<li><code>1 &lt;= piles[i]&nbsp;&lt;= 10<sup>4</sup></code></li>
</ul>

// class Solution {
// private:
// public:
//     int stoneGameII(vector<int>& piles) {
//         vector<int> prefixSum(piles.size());
//         int sum = 0;
//         for(int i=0;i<piles.size();i++){
//             sum += piles[i];
//             prefixSum[i] = sum;
//         }

//         int total = prefixSum.back();
//         cout<<total<<endl;

//         int index = 0;
//         int m = 1;
//         int alice = 1; //alice == 1 true , 0 == bob

//         while(true){
//             if(index >= piles.size()) break;
//             int minVal = INT_MAX;
//             int temp, M, limit;

//             for(int i=index ; i<piles.size() && i <= 2*m-1+index ; i++){
//                 int newM = max(m, i-index+1);
//                 // int last = min(piles.size()-1, 2*newM + i);
//                 int last = 2*newM + i;
//                 if(2*newM + i > piles.size()-1){
//                     last = piles.size()-1;
//                 }
//                 cout<<prefixSum[last] - prefixSum[i]<<endl;
//                 if(minVal >=  prefixSum[last] - prefixSum[i]){
//                     minVal = prefixSum[last] - prefixSum[i];
//                     temp =  i;
//                     M = newM;
//                     limit = last;
//                 }
//             }
//             cout<<minVal<<endl;

//             if(!alice){
//                 cout<<"minus content : "<<prefixSum[temp] - (index-1 >= 0 ? prefixSum[index-1] : 0)<<endl;
//                 total -= prefixSum[temp];
//                 total += (index-1 >= 0 ? prefixSum[index-1] : 0);
//                 index = temp + 1;
//                 m = M;
//                 alice = 1;
//             }
//             else{
//                 index = temp+1;
//                 m = M;
//                 alice = 0;
//             }
//             cout<<total<<" "<<index<<" "<<m<<endl;
//         }

//         return total;
//     }
// };


class Solution {
private:
    int call(int index, int turn, int m, vector<int> &piles, vector<vector<vector<int>>> &dp){
        if(index >= piles.size()) return 0;
        if(m>piles.size()/2) m = piles.size()/2;

        if(dp[index][m][turn] != -1) return dp[index][m][turn];

        int temp = (turn == 1) ? INT_MIN : INT_MAX;
        int val = 0;
        int newM;
        for(int i=index ; i<piles.size() && i<=2*m-1+index ; i++){
            val += piles[i];
            cout<<"hi"<<endl;
            newM = max(m, i-index+1);
            if(turn == 1){
                temp = max(temp, val + call(i+1, 0, newM, piles, dp));
            }
            else{
                temp = min(temp, call(i+1, 1, newM, piles, dp));
            }
        }
        return dp[index][m][turn] = temp;
    }

public:
    int stoneGameII(vector<int>& piles){
        int index = 0;
        int turn = 1;   //alice = 1, bob = 0;
        int m = 1;
        if(piles.size() == 1) return piles[0];
        else if(piles.size() == 2) return piles[0] + piles[1];
    
        vector<vector<vector<int>>> dp(piles.size()+1, vector<vector<int>>(piles.size()/2+1, vector<int>(2, -1)));
        int ans = call(index, turn, m, piles, dp);
        return ans;
    }
};
20766