1140.Stone Game II
===

###### tags: `Medium`,`Array`,`Math`,`DP`

[1140. Stone Game II](https://leetcode.com/problems/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]` <= 10^4^

### 解答

#### C++

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        ios_base::sync_with_stdio(0), cin.tie(0);
        int n = piles.size();
        if (n == 1) {
            return piles[0];
        } else if (n == 2) {
            return piles[0] + piles[1];
        }
        vector<int> suffixSum(n, 0);
        suffixSum[n - 1] = piles[n - 1];
        for (int i = n - 2; i >= 0; i --) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }
        vector<vector<int>> dp(n, vector(n, 0));
        play(piles, dp, suffixSum, 0, 1);
        return dp[0][1];
    }
    int play(vector<int>& piles, vector<vector<int>>& dp, vector<int>& suffixSum, int start, int M) {
        if (start == piles.size()) {
            return 0;
        }
        if (2 * M >= piles.size() - start) {
            return suffixSum[start];
        }
        if (dp[start][M]) {
            return dp[start][M];
        }
        int opponentScore = numeric_limits<int>::max();
        for (int m = 1; m <= 2 * M; m ++) {
            opponentScore = min(opponentScore, play(piles, dp, suffixSum, start + m, max(m, M)));
        }
        dp[start][M] = suffixSum[start] - opponentScore;
        return dp[start][M];
    }
};

> [name=Jerry Wu][time=Fri, 23 May, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)