leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0486.cpp (487B)

      1 class Solution {
      2     int dp[21][21];
      3 
      4     int rec(const vector<int> &nums, int i, int j) {
      5         if (i == j) return nums[i];
      6         if (dp[i][j] != -1) return dp[i][j];
      7 
      8         int left = nums[i] - rec(nums, i + 1, j);
      9         int right = nums[j] - rec(nums, i, j - 1);
     10 
     11         return dp[i][j] = max(left, right);
     12     }
     13 
     14   public:
     15     Solution() { memset(dp, 0xFF, sizeof(dp)); }
     16 
     17     bool PredictTheWinner(const vector<int> &nums) { return rec(nums, 0, nums.size() - 1) >= 0; }
     18 };