Skip to content

877. Stone Game

Approach 1: 2D DP

  • 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
class Solution {
 public:
  bool stoneGame(vector<int>& piles) {
    const int n = piles.size();
    // dp[i][j] := max stones you can get more than your opponent in piles[i..j]
    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 0; i < n; ++i)
      dp[i][i] = piles[i];

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
      }

    return dp[0][n - 1] > 0;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public boolean stoneGame(int[] piles) {
    final int n = piles.length;
    // dp[i][j] := max stones you can get more than your opponent in piles[i..j]
    int[][] dp = new int[n][n];

    for (int i = 0; i < n; ++i)
      dp[i][i] = piles[i];

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
      }

    return dp[0][n - 1] > 0;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def stoneGame(self, piles: List[int]) -> bool:
    n = len(piles)
    # dp[i][j] := max stones you can get more than your opponent in piles[i..j]
    dp = [[0] * n for _ in range(n)]

    for i, pile in enumerate(piles):
      dp[i][i] = pile

    for d in range(1, n):
      for i in range(n - d):
        j = i + d
        dp[i][j] = max(piles[i] - dp[i + 1][j],
                       piles[j] - dp[i][j - 1])

    return dp[0][n - 1] > 0

Approach 2: 1D DP

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  bool stoneGame(vector<int>& piles) {
    const int n = piles.size();
    vector<int> dp = piles;

    for (int d = 1; d < n; ++d)
      for (int j = n - 1; j - d >= 0; --j) {
        const int i = j - d;
        dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1]);
      }

    return dp[n - 1] > 0;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public boolean stoneGame(int[] piles) {
    final int n = piles.length;
    int[] dp = piles.clone();

    for (int d = 1; d < n; ++d)
      for (int j = n - 1; j - d >= 0; --j) {
        final int i = j - d;
        dp[j] = Math.max(piles[i] - dp[j], piles[j] - dp[j - 1]);
      }

    return dp[n - 1] > 0;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def stoneGame(self, piles: List[int]) -> bool:
    n = len(piles)
    dp = piles.copy()

    for d in range(1, n):
      for j in range(n - 1, d - 1, -1):
        i = j - d
        dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1])

    return dp[n - 1] > 0