Question

1140. Stone Game II

中文文档

Description

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

Solutions

Solution 1: Prefix Sum + Memoization Search

Since the player can take all the stones from the first $X$ piles each time, that is, they can take the stones from an interval, we can first preprocess a prefix sum array $s$ of length $n+1$, where $s[i]$ represents the sum of the first $i$ elements of the array piles.

Then we design a function $dfs(i, m)$, which represents the maximum number of stones that the current player can take when they can start from index $i$ of the array piles, and the current $M$ is $m$. Initially, Alice starts from index $0$, and $M=1$, so the answer we need to find is $dfs(0, 1)$.

The calculation process of the function $dfs(i, m)$ is as follows:

• If the current player can take all the remaining stones, the maximum number of stones they can take is $s[n] - s[i]$;
• Otherwise, the current player can take all the stones from the first $x$ piles of the remaining ones, where $1 \leq x \leq 2m$, and the maximum number of stones they can take is $s[n] - s[i] - dfs(i + x, max(m, x))$. That is to say, the number of stones that the current player can take is the number of all the remaining stones minus the number of stones that the opponent can take in the next round. We need to enumerate all $x$, and take the maximum value as the return value of the function $dfs(i, m)$.

To avoid repeated calculations, we can use memoization search.

Finally, we return $dfs(0, 1)$ as the answer.

The time complexity is $O(n^3)$, and the space complexity is $O(n^2)$. Here, $n$ is the length of the array piles.

class Solution:
  def stoneGameII(self, piles: List[int]) -> int:
    @cache
    def dfs(i, m):
      if m * 2 >= n - i:
        return s[n] - s[i]
      return max(
        s[n] - s[i] - dfs(i + x, max(m, x)) for x in range(1, m << 1 | 1)
      )

    n = len(piles)
    s = list(accumulate(piles, initial=0))
    return dfs(0, 1)

class Solution {
  private int[] s;
  private Integer[][] f;
  private int n;

  public int stoneGameII(int[] piles) {
    n = piles.length;
    s = new int[n + 1];
    f = new Integer[n][n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + piles[i];
    }
    return dfs(0, 1);
  }

  private int dfs(int i, int m) {
    if (m * 2 >= n - i) {
      return s[n] - s[i];
    }
    if (f[i][m] != null) {
      return f[i][m];
    }
    int res = 0;
    for (int x = 1; x <= m * 2; ++x) {
      res = Math.max(res, s[n] - s[i] - dfs(i + x, Math.max(m, x)));
    }
    return f[i][m] = res;
  }
}

class Solution {
public:
  int stoneGameII(vector<int>& piles) {
    int n = piles.size();
    int s[n + 1];
    s[0] = 0;
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + piles[i];
    }
    int f[n][n + 1];
    memset(f, 0, sizeof f);
    function<int(int, int)> dfs = [&](int i, int m) -> int {
      if (m * 2 >= n - i) {
        return s[n] - s[i];
      }
      if (f[i][m]) {
        return f[i][m];
      }
      int res = 0;
      for (int x = 1; x <= m << 1; ++x) {
        res = max(res, s[n] - s[i] - dfs(i + x, max(x, m)));
      }
      return f[i][m] = res;
    };
    return dfs(0, 1);
  }
};

func stoneGameII(piles []int) int {
  n := len(piles)
  s := make([]int, n+1)
  f := make([][]int, n+1)
  for i, x := range piles {
    s[i+1] = s[i] + x
    f[i] = make([]int, n+1)
  }
  var dfs func(i, m int) int
  dfs = func(i, m int) int {
    if m*2 >= n-i {
      return s[n] - s[i]
    }
    if f[i][m] > 0 {
      return f[i][m]
    }
    f[i][m] = 0
    for x := 1; x <= m<<1; x++ {
      f[i][m] = max(f[i][m], s[n]-s[i]-dfs(i+x, max(m, x)))
    }
    return f[i][m]
  }
  return dfs(0, 1)
}

function stoneGameII(piles: number[]): number {
  const n = piles.length;
  const f = Array.from({ length: n }, _ => new Array(n + 1).fill(0));
  const s = new Array(n + 1).fill(0);
  for (let i = 0; i < n; ++i) {
    s[i + 1] = s[i] + piles[i];
  }
  const dfs = (i: number, m: number) => {
    if (m * 2 >= n - i) {
      return s[n] - s[i];
    }
    if (f[i][m]) {
      return f[i][m];
    }
    let res = 0;
    for (let x = 1; x <= m * 2; ++x) {
      res = Math.max(res, s[n] - s[i] - dfs(i + x, Math.max(m, x)));
    }
    return (f[i][m] = res);
  };
  return dfs(0, 1);
}

Solution 2

class Solution:
  def stoneGameII(self, piles: List[int]) -> int:
    @cache
    def dfs(i: int, m: int = 1) -> int:
      if i >= len(piles):
        return 0
      t = inf
      for x in range(1, m << 1 | 1):
        t = min(t, dfs(i + x, max(m, x)))
      return s[-1] - s[i] - t

    s = list(accumulate(piles, initial=0))
    return dfs(0)