leetcode

0

1 // Return true works as Alice is always the winner

2 class Solution {

3 int dp[501][501];

4 int score(const vector<int> &piles, int i, int j, int crnt) {

5 if (j < i) return 0;

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

7 return dp[i][j] = max(score(piles, i + 1, j, -(crnt + piles[i])),

8 score(piles, i, j - 1, -(crnt + piles[j])));

9 }

10

11 public:

12 Solution() { memset(dp, 0xFF, sizeof(dp)); }

13 bool stoneGame(const vector<int> &piles) { return score(piles, 0, piles.size() - 1, 0) <= 0; }

14 };