leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1690.cpp (684B)

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