<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>

/*
There are a number of piles arranged in a row

each pile has a positive integer number of stones piles[i]

objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first.  Initially, M = 1.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M
Then, we set M = max(M, X).

The game continues until all the stones have been taken.

eturn the maximum number of stones Alice can get.
*/

class Solution {
    bool isAlice = true;

    pair<int, int> getMaxPossibleStones (
            vector<int> &pileList,
            int m,
            int position,
            vector<vector<pair<int, int>>> &minWaysCache
        ) {
        int pileListLen = pileList.size();

        if (pileListLen - 1 == position) return {pileList[position], 0};
        if (position == pileListLen) return {0, 0};


        int allowedTakePileCount = min ( 2 * m, pileListLen);

        if (minWaysCache[position][allowedTakePileCount].first != -1) return minWaysCache[position][allowedTakePileCount];

        int maxStoneCountCurrent = 0;
        int maxStoneCountOther = INT_MAX;

        int stonePileCount = 0;

        for (int i = position; (i - position) < allowedTakePileCount && i < pileListLen; i++) {
            int currentPileStoneCount = pileList[i];

            stonePileCount += currentPileStoneCount;

            pair<int, int> maxPossibleStoneCount = getMaxPossibleStones (pileList, max (i - position + 1, m), i+1, minWaysCache);

            int maxPossibleStoneCountA = maxPossibleStoneCount.first;
            int maxPossibleStoneCountB = maxPossibleStoneCount.second;

            if (maxPossibleStoneCountB + stonePileCount > maxStoneCountCurrent) {
                maxStoneCountCurrent = stonePileCount + maxPossibleStoneCountB;
                maxStoneCountOther = maxPossibleStoneCountA;
            }
        }

        return minWaysCache[position][allowedTakePileCount] = {maxStoneCountCurrent, maxStoneCountOther};
    }
public:
    int stoneGameII(vector<int>& piles) {
        int pileListLen = piles.size();
        const int maxPossibleLen = 100;

        vector<vector<pair<int, int>>> minWaysCache(
            maxPossibleLen, 
            vector<pair<int, int>>(
                maxPossibleLen,
                {-1, -1}
        )
    );

    pair<int, int> maxPossibleStoneCount = getMaxPossibleStones(piles, 1, 0, minWaysCache);


        return maxPossibleStoneCount.first;
    }
};
21013