class Solution {
public:
int stoneGameVII(vector<int>& stones) {
const int n = stones.size();
// dp[i][j] := the maximum score you can get more than your opponent in
// stones[i..j]
dp.resize(n, vector<int>(n));
prefix.resize(n + 1);
partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);
return stoneGameVII(stones, 0, n - 1);
}
private:
vector<vector<int>> dp;
vector<int> prefix;
int stoneGameVII(const vector<int>& stones, int i, int j) {
if (i == j)
return 0;
if (dp[i][j] > 0)
return dp[i][j];
dp[i][j] =
max({dp[i][j],
// Remove stones[i], so get the sum of stones[i + 1..j]
prefix[j + 1] - prefix[i + 1] - stoneGameVII(stones, i + 1, j),
// Remove stones[j], so get the sum of stones[i..j - 1]
prefix[j] - prefix[i] - stoneGameVII(stones, i, j - 1)});
return dp[i][j];
}
};