leetcode

0 class Solution {

1 int dp[10001][101];

2

3 public:

4 Solution() { memset(dp, 0, sizeof(dp)); }

5

6 int stoneGameII(const vector<int> &piles) {

7 int n = piles.size();

8 vector<int> sum(n + 1, 0);

9 for (int i = n - 1; i >= 0; i--) {

10 dp[i][n] = sum[i] = sum[i + 1] + piles[i];

11 }

12

13 for (int i = n - 1; i >= 0; i--) {

14 for (int j = n - 1; j >= 1; j--) {

15 for (int X = 1; X <= 2 * j && i + X <= n; X++) {

16 dp[i][j] = max(dp[i][j], sum[i] - dp[i + X][max(j, X)]);

17 }

18 }

19 }

20 return dp[0][1];

21 }

22 };