# 1140. Stone Game II
###### tags: `Leetcode` `Medium` `Backtracking` `Min-Max Strategy`
Link: https://leetcode.com/problems/stone-game-ii/
## 思路

显然答案就是```memo[0][1]```
那么如何计算```memo[i][m]```呢？
当```M=m```并且我们从第```idx```个piles开始拿的时候我们可以拿```1～2*m```个piles
假设我们拿了```i```个piles对手一定从```idx+i```开始拿 所以```memo[idx+i][min(m,i)]```就会是他拿的数量
所以截止游戏时能得到的最大收益就是```sufSum[idx] - solve(idx+i, max(i,m))```
对于所有的```i``` 我们只需要取可以让```sufSum[idx] - solve(idx+i, max(i,m))```最大的那个即可
## Code

class Solution {
public int stoneGameII(int[] piles) {
int n = piles.length;
int[][] memo = new int[101][101];
int[] postSum = new int[n];
postSum[n-1] = piles[n-1];
for(int i=n-2; i>=0; i--){
postSum[i] = postSum[i+1]+piles[i];
}
return solve(0, 1, memo, postSum);
}
private int solve(int idx, int m, int[][] memo, int[] postSum){
if(idx==postSum.length) return 0;
if(memo[idx][m]!=0) return memo[idx][m];
for(int i=1; i<=2*m && idx+i<=postSum.length; i++){
memo[idx][m] = Math.max(memo[idx][m], postSum[idx]-solve(idx+i, Math.max(m, i), memo, postSum));
}
return memo[idx][m];
}
}