1
class Solution {
2
 public:
3
  int solve(vector<int> &piles, int i, int j, vector<vector<int>> &dp) {
4
    if (i == j) return piles[i];
5

6
    if (dp[i][j] != -1) return dp[i][j];
7

8
    return dp[i][j] = max((piles[i] + solve(piles, i + 1, j, dp)),
9
                          (piles[j] + solve(piles, i, j - 1, dp)));
10
  }
11

12
  bool stoneGame(vector<int> &piles) {
13
    int n = piles.size();
14
    vector<vector<int>> dp(n, vector<int>(n, -1));
15
    return solve(piles, 0, n - 1, dp);
16
  }
17
};