leetcode

0 class Solution {

1 static int dp[1001][1001];

2

3 static int solve(const vector<int> &stones, int i, int j, int sum) {

4 if (i > j) return 0;

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

6

7 const int a = sum - stones[i] - solve(stones, i + 1, j, sum - stones[i]);

8 const int b = sum - stones[j] - solve(stones, i, j - 1, sum - stones[j]);

9

10 return dp[i][j] = max(a, b);

11 }

12

13 public:

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

15 int stoneGameVII(const vector<int> &stones) const {

16 const int sum = accumulate(begin(stones), end(stones), 0);

17 return solve(stones, 0, size(stones) - 1, sum);

18 }

19 };

20

21 int Solution::dp[1001][1001];