LeetCode/1140.stone-game-ii.cpp at master · CSUwangj/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
 * @lc app=leetcode id=1140 lang=cpp
 *
 * [1140] Stone Game II
 */

// @lc code=start
auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();

class Solution {
public:
  int stoneGameII(vector<int>& piles) {
    int len = piles.size();
    vector<int> suffixSum(len + 1);
    for(int i = len - 1; i >= 0; --i) {
      suffixSum[i] = suffixSum[i + 1] + piles[i];
    }
    vector<vector<int>> dp(len + 1, vector<int>(len + 1));
    for(int i = 0; i <= len; ++i) {
      dp[i][len] = suffixSum[i];
    }
    for(int i = len - 1; i >= 0; --i) {
      for(int j = len - 1; j >= 1; --j) {
        for(int X = 1; X <= 2 * j && X + i <= len; ++X) {
          dp[i][j] = max(dp[i][j], suffixSum[i] - dp[i + X][max(j, X)]);
        }
      }
    }

    return dp[0][1];
  }
};

// Accepted
// 92/92 cases passed (140 ms)
// Your runtime beats 22.12 % of cpp submissions
// Your memory usage beats 48.08 % of cpp submissions (10.1 MB)
// @lc code=end