Skip to content

1140. Stone Game II

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 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
class Solution {
 public:
  int stoneGameII(vector<int>& piles) {
    const int n = piles.size();
    vector<vector<int>> mem(n, vector<int>(n));
    vector<int> suffix = piles;  // suffix[i] := sum(piles[i..n))
    for (int i = n - 2; i >= 0; --i)
      suffix[i] += suffix[i + 1];
    return stoneGameII(suffix, 0, 1, mem);
  }

 private:
  // Returns the maximum number of stones Alice can get from piles[i..n) with M.
  int stoneGameII(const vector<int>& suffix, int i, int M,
                  vector<vector<int>>& mem) {
    if (i + 2 * M >= mem.size())
      return suffix[i];
    if (mem[i][M] > 0)
      return mem[i][M];

    int opponent = suffix[i];

    for (int X = 1; X <= 2 * M; ++X)
      opponent = min(opponent, stoneGameII(suffix, i + X, max(M, X), mem));

    return mem[i][M] = suffix[i] - opponent;
  }
};

 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
class Solution {
  public int stoneGameII(int[] piles) {
    final int n = piles.length;
    int[][] mem = new int[n][n];
    int[] suffix = new int[n]; // suffix[i] := sum(piles[i..n))
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, -1));
    suffix[n - 1] = piles[n - 1];
    for (int i = n - 2; i >= 0; --i)
      suffix[i] = suffix[i + 1] + piles[i];
    return stoneGameII(suffix, 0, 1, mem);
  }

  // Returns the maximum number of stones Alice can get from piles[i..n) with M.
  private int stoneGameII(int[] suffix, int i, int M, int[][] mem) {
    if (i + 2 * M >= suffix.length)
      return suffix[i];
    if (mem[i][M] != -1)
      return mem[i][M];

    int opponent = suffix[i];

    for (int X = 1; X <= 2 * M; ++X)
      opponent = Math.min(opponent, stoneGameII(suffix, i + X, Math.max(M, X), mem));

    return mem[i][M] = suffix[i] - opponent;
  }
}