Leetcode 1140. Stone Game II

https://leetcode.com/problems/stone-game-ii/description/


Notes:

This is a question about optimal games, so usually it is about the so-called minMax algorithm. Similar questions have been seen before frequently, like two players pick up coins optimally from an array of coins.

But for this question, they can only pick up from one side, which means one index should be enough to record the process, since the other side is always the end. The second parameter is M, or the maximum number of piles that one player can pick up.

If Alex pick up 1 pile, then the parameters becomes (1, 1) for Lee, where the first one is index and the second one is M. Then Lee can either pick one pile or two piles (if there are two piles). Then it backs to Alex.

Similarly, if Alex pick up 2 pile, then the parameters becomes (2, 2) for Lee, where the first one is index and the second one is M. Then Lee can make a choice from 1 to 4 piles (if there are enough piles). Then it backs to Alex.

The key of the minMax algorithm is that Alex will always choose the maximum among all his choices (the same as Lee), and then Lee will always leave the minimum of the rest choices to Alex when it switches back to Alex (the same as Alex leaves to Lee). 

Obviously, when one player make one move, the size the question becomes smaller and it is the still the same question. This is exactly when we can apply the recursion trick.

To reduce redundant calculation, we can choose either dp or memorization. The purpose is the same: we only need to calculation once for one case.

See the code below using memorization:

class Solution {
public:
    int stoneGameII(vector& piles) {
        int len = piles.size();
        vector> memo(len, vector(len, -1));
        dfs(piles, 0, 1, memo);
        return memo[0][1];
    }
private:
    int dfs(vector &ps, int x, int m, vector> &ms) {
        if(x>=ps.size()) return 0;
        if(ms[x][m] != -1) return ms[x][m];
        if(x+1==ps.size()) {
            ms[x][m] = ps[x];
            return ms[x][m];
        }
        int t = 0, sum = 0;
        for(int i=x; i<=min(x+2*m-1, (int)ps.size()-1); ++i) {//pay attention to boundary conditions
            sum += ps[i];
            int d = 1e6;
            for(int j=i+1; j<=min(i+1+2*max(m, i-x+1)-1, (int)ps.size()-1); ++j) {
                d = min(d, dfs(ps, j+1, max(max(m, i-x+1), j-i), ms));
            }
            if(d == 1e6) d = 0;//if there is no change of d, it means no element left
            t = max(t, sum + d);
        }
        ms[x][m] = t;
        return ms[x][m];
    }
};

Follow up question: 

How about the players can pick up piles from both sides?