# 0877. Stone Game
###### tags: `Leetcode` `Medium` `Min-Max Strategy` `Backtracking`
Link: https://leetcode.com/problems/stone-game/
## 思路
### 思路一
先拿的人可以确保自己拿的数量总和是奇数 因为一定会赢
### 思路二

如果现在剩下的piles index是从```s```到```e```
如果```s==e``` 直接拿走这一堆
否则看拿走```s```获得的石头多 还是拿走```e```获得的石头多
拿走```s```获得的石头数等于从```s```到```e```的总石头数-对手能拿走的石头数
## Code
### 思路一

class Solution {
public boolean stoneGame(int[] piles) {
return true;
}
}

### 思路二

class Solution {
public boolean stoneGame(int[] piles) {
int n = piles.length;
int[][] dp = new int[n][n];
int[] prefixSum = new int[n];

prefixSum[0] = piles[0];
for(int i=1; i<n; i++) prefixSum[i] = prefixSum[i-1]+piles[i];
int total = prefixSum[n-1];

int myBest = dfs(0, n-1, piles, dp, prefixSum);
return myBest>total-myBest;
}
private int dfs(int s, int e, int[] piles, int[][] dp, int[] prefixSum){
if(s==e) return dp[s][e] = piles[s];
if(dp[s][e]!=0) return dp[s][e];
int sum = prefixSum[e]-(s==0?0:prefixSum[s-1]);
dp[s][e] = Math.max(sum-dfs(s+1, e, piles, dp, prefixSum), sum-dfs(s, e-1, piles, dp, prefixSum));
return dp[s][e];
}
}