• Time:O(n^2)
• Space:O(n^2)

## C++

``````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;
}
};
``````

## JAVA

``````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;
}
}
``````

## Python

``````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
``````

• Time:O(n^2)
• Space:O(n)

## C++

``````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;
}
};
``````

## JAVA

``````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;
}
}
``````

## Python

``````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
``````