leetcode

0 class Solution {

1 int dp[21][21];

2

3 int rec(const vector<int> &nums, int i, int j) {

4 if (i == j) return nums[i];

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

6

7 int left = nums[i] - rec(nums, i + 1, j);

8 int right = nums[j] - rec(nums, i, j - 1);

9

10 return dp[i][j] = max(left, right);

11 }

12

13 public:

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

15

16 bool PredictTheWinner(const vector<int> &nums) { return rec(nums, 0, nums.size() - 1) >= 0; }

17 };