leetcode

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

1690.cpp (684B)

      1 class Solution {
      2     static int dp[1001][1001];
      3 
      4     static int solve(const vector<int> &stones, int i, int j, int sum) {
      5         if (i > j) return 0;
      6         if (dp[i][j] != -1) return dp[i][j];
      7 
      8         const int a = sum - stones[i] - solve(stones, i + 1, j, sum - stones[i]);
      9         const int b = sum - stones[j] - solve(stones, i, j - 1, sum - stones[j]);
     10 
     11         return dp[i][j] = max(a, b);
     12     }
     13 
     14   public:
     15     Solution() { memset(dp, 0xFF, sizeof(dp)); }
     16     int stoneGameVII(const vector<int> &stones) const {
     17         const int sum = accumulate(begin(stones), end(stones), 0);
     18         return solve(stones, 0, size(stones) - 1, sum);
     19     }
     20 };
     21 
     22 int Solution::dp[1001][1001];