---
# System prepended metadata

title: 1406. Stone Game III
tags: [Leetcode, Min-Max Strategy, Hard, Backtracking]

---

# 1406. Stone Game III
###### tags: `Leetcode` `Hard` `Backtracking` `Min-Max Strategy`
Link: https://leetcode.com/problems/stone-game-iii/
## 思路
先算出alice最多能获得多少value
然后就可以算出bob有多少value
比较一下即可得出答案
```dp[i]```表示当stone只剩下```[i:]```的时候player最多能拿到多少value
由于value可能是负的 所以dp的初始值需要设成```Integer.MIN_VALUE```
## Code
```java=
class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] sum = new int[n];
        
        sum[0] = stoneValue[0];
        for(int i=1; i<n; i++) sum[i] = stoneValue[i]+sum[i-1];
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MIN_VALUE);
        int total = sum[n-1];
        
        int first = dfs(dp, stoneValue, sum, 0);
        
        if(total-first==first) return "Tie";
        else if(total-first>first) return "Bob";
        else return "Alice";
    }
    private int dfs(int[] dp, int[] stoneValue, int[] sum, int start){
        int n = dp.length;
        if(start == n) return 0;
        if(dp[start]!=Integer.MIN_VALUE) return dp[start];
        int totalSum = sum[n-1]-(start==0?0:sum[start-1]);
        for(int i=1; i<=3; i++){
            if(start+i>n) break;
            dp[start] = Math.max(dp[start], totalSum-dfs(dp, stoneValue, sum, start+i));
        }
        return dp[start];
    }
}
```