1140. Stone Game II

Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The 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.

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

class Solution {
    vector<vector<int>> dp;
    int calc(vector<int>& p, int pos, int m) {
        if(pos + 2 * m >= p.size()) return p[pos];
        if(dp[pos][m] != -1) return dp[pos][m];
        for(int i = pos + 1; i <= pos + m * 2; i++) {
            dp[pos][m] = max(dp[pos][m], p[pos] - calc(p, i, max(m, i - pos)));
        }
        return dp[pos][m];
    }
public:
    int stoneGameII(vector<int>& p) {
        dp = vector<vector<int>> (p.size(), vector<int>(p.size(), -1));
        partial_sum(rbegin(p), rend(p), rbegin(p), plus<int>());
        return calc(p, 0, 1);
    }
};