0877.cpp (548B)
1 2 // Return true works as Alice is always the winner 3 class Solution { 4 int dp[501][501]; 5 int score(const vector<int> &piles, int i, int j, int crnt) { 6 if (j < i) return 0; 7 if (dp[i][j] != -1) return dp[i][j]; 8 return dp[i][j] = max(score(piles, i + 1, j, -(crnt + piles[i])), 9 score(piles, i, j - 1, -(crnt + piles[j]))); 10 } 11 12 public: 13 Solution() { memset(dp, 0xFF, sizeof(dp)); } 14 bool stoneGame(const vector<int> &piles) { return score(piles, 0, piles.size() - 1, 0) <= 0; } 15 };