# 1140.Stone-Game-II

## 1140. Stone Game II

## 题目地址

<https://leetcode.com/problems/stone-game-ii/> <https://www.acwing.com/solution/LeetCode/content/3172/>

## 题目描述

```
Alex and Lee 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. 

Alex and Lee take turns, with Alex 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 Alex and Lee play optimally, return the maximum number of stones Alex can get.

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

Constraints:
1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4
```

## 代码

### Approach #1 DFS with memorization

Time: O(1) && Space: O(1)

```java
class Solution {
  int[] sums;
  int[][] dp;
  public int stoneGameII(int[] piles) {
        if (piles == null || piles.length == 0) {
      return 0;
    }
    int n = piles.length;
    dp = new int[n][n];

    sums = new int[n];
    sums[n-1] = piles[n-1];
    for (int i = n - 2; i >= 0; i--) {
      sums[i] = sums[i+1] + piles[i];
    }
    return helper(piles, 0, 1);
  }

  private int helper(int[] a, int i, int M) {
    if (i == a.length)        return 0;
    if (2*M >= a.length - i) {
      return sum[i];
    }
    if (dp[i][M] != 0)        return dp[i][M];
    int min = Integer.MAX_VALUE; // the min value the next player can get
    for (int x = 1; x <= 2 * M; x++) {
      min = Math.min(min, helper(a, i+x, Math.max(M, x));)
    }
    dp[i][M] = sums[i] - min; // max stones = all the left stones - the min stones next player can get
    return dp[i][M];
  }
}
```

### Approach #2 DP

Let `DP[i][m]` be the maximal number of stones a player can get when i is the current position and the current `M` is `m`.

1. If the player takes only the first pile (piles\[i], `x` = 1), the other player can get up to `DP[i+1][max(m, 1)]`. So the current player can get `Si - DP[i+1][max(m, 1)]`.
2. If the player takes the first two piles (piles\[i], piles\[i+1], `x` = 2), the other player can get up to `DP[i+2][max(m, 2)]`. So the current player can get `Si - DP[i+2][max(m, 2)]`.
3. ...
4. If the player takes the first `2m` piles (piles\[i], piles\[i+1], ..., piles\[i+2m], `x` = 2m), the other player can get up to `DP[i+2m][max(m, 2m)]`. So the current player can get `Si - DP[i+2m][max(m, 2m)]`.

Time: `O(n^3)`, 状态数`O(n^2)`，转移需要`O(n)`的时间 Space: `O(n^2)`

```java
class Solution {
  public int stoneGameII(int[] piles) {
    int n = piles.length;
    for (int i  = n - 2; i >= 0; i--) {
      piles[i] += piles[i+1];
    }
    if (n <= 2) {
      return piles[0];
    }
    int[][] dp = new int[n][(n+1)/2 + 1];
    for (int i = n-1; i >= 0; i--) {
      int sum = piles[i];
      int m = (n-i+1) / 2;
      dp[i][m] = sum;
      while (--m >= 1) {
        dp[i][m] = 0;
        for (int x = 1; x <= m*2 && i+x < n; x++) {
          int max = Math.min((n-i-x+1)/2, Math.max(x, m));
          dp[i][m] = Math.max(dp[i][m], sum - dp[i+x][max]);
        }
      }
    }
    return dp[0][1];
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/dynamic-programming/1140.stone-game-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.