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