# 1406. Stone Game III
###### tags: `Leetcode` `Hard` `Backtracking` `Min-Max Strategy`
Link: https://leetcode.com/problems/stone-game-iii/
## 思路
先算出alice最多能获得多少value
然后就可以算出bob有多少value
比较一下即可得出答案

由于value可能是负的 所以dp的初始值需要设成```Integer.MIN_VALUE```
## Code

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