1
class Solution {
2
 public:
3
  int dp[501][501];
4

5
  int f(vector<int> &v, int i, int j) {
6
    if (i >= j) return 0;
7

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

10
    int r = 0;
11
    for (int k = i; k <= j; k++) r += v[k];
12

13
    int l = 0, ans = 0;
14
    for (int k = i; k <= j; k++) {
15
      l += v[k];
16
      r -= v[k];
17
      if (l < r)
18
        ans = max(ans, l + f(v, i, k));
19
      else if (r < l)
20
        ans = max(ans, r + f(v, k + 1, j));
21
      else
22
        ans = max(ans, max(l + f(v, i, k), r + f(v, k + 1, j)));
23
    }
24
    return dp[i][j] = ans;
25
  }
26

27
  int stoneGameV(vector<int> &stoneValue) {
28
    memset(dp, -1, sizeof(dp));
29
    return f(stoneValue, 0, stoneValue.size() - 1);
30
  }
31
};