1
class Solution {
2
 public:
3
  bool PredictTheWinner(vector<int> &nums) {
4
    vector<vector<vector<int>>> dp(nums.size(),
5
                                   vector<vector<int>>(nums.size(), vector<int>(3, INT_MAX)));
6
    int t = fun(dp, nums, 0, nums.size() - 1, 1);
7
    return t >= 0;
8
  }
9
  int fun(vector<vector<vector<int>>> &dp, vector<int> &v, int i, int j, int t) {
10
    if (i > j) return 0;
11

12
    if (dp[i][j][t + 1] != INT_MAX) return dp[i][j][t + 1];
13

14
    if (t > 0)
15
      return dp[i][j][t + 1] =
16
                 max(v[i] * t + fun(dp, v, i + 1, j, -1), v[j] * t + fun(dp, v, i, j - 1, -1));
17
    else
18
      return dp[i][j][t + 1] =
19
                 min(v[i] * t + fun(dp, v, i + 1, j, 1), v[j] * t + fun(dp, v, i, j - 1, 1));
20
  }
21
};