<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 {
public:

    int rec(int s, int m, int step, vector<int>& p, map<pair<int, pair<int, int>>, int>& dp) {

        int a = INT_MAX, b = INT_MAX;
        int av = 0;
        if (dp[{step % 2, {s, m}}]) return dp[{step % 2, {s, m}}];
        // if (s + (2 * m) >= p.size() - 1) {
        //     if (step % 2 == 0) {
        //         av += (p[p.size() - 1] - p[s - 1]);
        //     }
        //     return av;
        // }

        if (step % 2 == 0) {
            a = INT_MIN, b = 0;
        }

        for (int i = 1; i <= 2 * m && s + i <= p.size(); i++) {
            int sum = p[s + i - 1] - p[s - 1];
            int nm = max(m, i);

            if (step % 2 == 0) b = max(b, sum + rec(s + i, nm, step + 1, p, dp));
            if (step % 2 == 1) b = min(b, rec(s + i, nm, step + 1, p, dp));

            // b = step % 2 == 0 ? max(a, b): min(a, b);
        }

        dp[{step % 2, {s, m}}] = b == INT_MAX ? 0 : b;

        return dp[{step % 2, {s, m}}];

    }

    int stoneGameII(vector<int>& piles) {

        vector<int> ps(piles.size(), 0);
        map<pair<int, pair<int, int>>, int> dp;

        int a = 0, b = 0;

        ps[0] = piles[0];
        for(int i = 1; i < piles.size(); i++) {
            ps[i] = ps[i - 1] + piles[i];
        }
        
        a = ps[0] + rec(1, 1, 1, ps, dp); //current index, m, step number, alice stones, bob stones, prefix sum vector
        if (ps.size() > 1) b = ps[1] + rec(2, 2, 1, ps, dp);

        return max(a, b);

    }
};
22993