---
# System prepended metadata

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

---

# 1140. Stone Game II
###### tags: `Leetcode` `Medium` `Backtracking` `Min-Max Strategy`
Link: https://leetcode.com/problems/stone-game-ii/
## 思路
```memo[idx][m]```表示当```M=m```时从第```idx```个piles开始拿最多能拿多少石头
显然答案就是```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
```java=
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];
    }
}
```