---
# System prepended metadata

title: 0877. Stone Game
tags: [Leetcode, Min-Max Strategy, Medium, Backtracking]

---

# 0877. Stone Game
###### tags: `Leetcode` `Medium` `Min-Max Strategy` `Backtracking`
Link: https://leetcode.com/problems/stone-game/
## 思路
### 思路一
先拿的人可以确保自己拿的数量总和是奇数 因为一定会赢
### 思路二
```dp[s][e]```代表player在剩的piles index是从```s```到```e```的时候拿走的最多的石头数
如果现在剩下的piles index是从```s```到```e```
如果```s==e``` 直接拿走这一堆
否则看拿走```s```获得的石头多 还是拿走```e```获得的石头多
拿走```s```获得的石头数等于从```s```到```e```的总石头数-对手能拿走的石头数
## Code
### 思路一
```java=
class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}
```
### 思路二
```java=
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];
    }
}
```
