1
class Solution {
2
 public:
3
  int dp[103][103][2];
4
  int rec(int i, int m, int p, vector<int> &piles) {
5
    if (i == piles.size()) return 0;
6
    if (dp[i][m][p] != -1) return dp[i][m][p];
7
    int cnt = 0, ans = INT_MIN, n = piles.size();
8
    for (int j = i; j < min(n, i + 2 * m); j++) {
9
      cnt += piles[j];
10
      ans = max(ans, cnt - rec(j + 1, max(j - i + 1, m), 1 - p, piles));
11
    }
12
    return dp[i][m][p] = ans;
13
  }
14
  int stoneGameII(vector<int> &piles) {
15
    int sum = 0;
16
    memset(dp, -1, sizeof(dp));
17
    for (auto i : piles) sum += i;
18
    return (sum + rec(0, 1, 0, piles)) / 2;
19
  }
20
};