Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 20

Description

Stone Game II

Alice and Bob continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones. 

Alice and Bob take turns, with Alice starting first.  Initially, M = 1.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

Example 2:

Input: piles = [1,2,3,4,5,100]
Output: 104

Constraints:

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 104

Solution

class Solution {
  int dp[101][32];
  int dfs(const vector<int> &prefix, int pos, int m, int result = INT_MIN) {
    if(pos + m * 2 > prefix.size()) return prefix.back() - (pos ? prefix[pos - 1] : 0);
    if(dp[pos][m]) return dp[pos][m];
    for(int i = pos; i < pos + m * 2; ++i) {
      result = max(result, prefix[i] - (pos ? prefix[pos - 1] : 0) - dfs(prefix, i + 1, max(m, i - pos + 1)));
    }
    dp[pos][m] = result;
    return result;
  }
public:
  int stoneGameII(vector<int>& piles) {
    partial_sum(piles.begin(), piles.end(), piles.begin());
    return (piles.back() + dfs(piles, 0, 1)) / 2;
  }
};

// Accepted
// 92/92 cases passed (4 ms)
// Your runtime beats 99.55 % of cpp submissions
// Your memory usage beats 80.14 % of cpp submissions (8.4 MB)