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
29
30
31
32
33
class Solution {
 public:
  int stoneGameII(vector<int>& piles) {
    const int n = piles.size();
    // dp[i][j] := max # of stones Alice can get w/ piles[i:] and M = j
    dp.resize(n, vector<int>(n));
    // suffixSum[i] := sum of piles[i:]
    suffixSum = piles;

    for (int i = n - 2; i >= 0; --i)
      suffixSum[i] += suffixSum[i + 1];

    return stoneGameII(0, 1);
  }

 private:
  vector<vector<int>> dp;
  vector<int> suffixSum;

  int stoneGameII(int i, int M) {
    if (i + 2 * M >= dp.size())
      return suffixSum[i];
    if (dp[i][M])
      return dp[i][M];

    int opponent = suffixSum[i];

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

    return dp[i][M] = suffixSum[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
28
29
30
31
class Solution {
  public int stoneGameII(int[] piles) {
    final int n = piles.length;
    // dp[i][j] := max # of stones Alice can get w/ piles[i:] and M = j
    dp = new int[n][n];
    // suffixSum[i] := sum of piles[i:]
    suffixSum = piles.clone();

    for (int i = n - 2; i >= 0; --i)
      suffixSum[i] += suffixSum[i + 1];

    return stoneGameII(0, 1);
  }

  private int[][] dp;
  private int[] suffixSum;

  private int stoneGameII(int i, int M) {
    if (i + 2 * M >= dp.length)
      return suffixSum[i];
    if (dp[i][M] > 0)
      return dp[i][M];

    int opponent = suffixSum[i];

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

    return dp[i][M] = suffixSum[i] - opponent;
  }
}