Alex and Lee continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones. 
Alex and Lee take turns, with Alex starting first.  Initially, M = 1.
On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).
The game continues until all the stones have been taken.
Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.
Example 1:
Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 
Constraints:
1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @lru_cache(maxsize=None)
        def minimax(st, m, player):
            if st >= len(piles): return 0
            if player:
                return max([sum(piles[st:st+x]) + minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
            else:
                return min([minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
        return minimax(0, 1, 1)        

# [NOTE] Really good explanation here:
# https://leetcode.com/problems/stone-game-ii/discuss/345222/Python-Minimax-DP-solution
# The idea of minimax :
# If am the player 1 (whose winning sum we are trying to calculate), then I recurse on all possibilities and get the max.
# If am the player 2 (the opponent), then I try to minimize what P1 gets, and since we are not interested in what score P2 gets, we only calculate the min(all P1 next moves) and dont include the score P2 gets.
# Thanks to @douzigege for his comment which explains the minimax scenario specifically for this problem.

# if player == 1st player,
# gain = first x piles + minimax(..., 2nd player), where the gain is maximized
# if player == 2nd player,
# gain = 0 + minimax(..., 1st player), where the gain is minimized because the 2nd player tries to maximize this

# TLE for this input without@lru_cache
# [8270,7145,575,5156,5126,2905,8793,7817,5532,5726,7071,7730,5200,5369,5763,7148,8287,9449,7567,4850,1385,2135,1737,9511,8065,7063,8023,7729,7084,8407]

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        @lru_cache(maxsize=None)
        def minimax(st, m, player):
            if st >= len(piles): return 0
            if player:
                return max([sum(piles[st:st+x]) + minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
            else:
                return min([minimax(st+x, max(m,x), player^1) for x in range(1, 2*m+1)])
        return minimax(0, 1, 1)        

# [NOTE] Really good explanation here:
# https://leetcode.com/problems/stone-game-ii/discuss/345222/Python-Minimax-DP-solution
# The idea of minimax :
# If am the player 1 (whose winning sum we are trying to calculate), then I recurse on all possibilities and get the max.
# If am the player 2 (the opponent), then I try to minimize what P1 gets, and since we are not interested in what score P2 gets, we only calculate the min(all P1 next moves) and dont include the score P2 gets.
# Thanks to @douzigege for his comment which explains the minimax scenario specifically for this problem.

# if player == 1st player,
# gain = first x piles + minimax(..., 2nd player), where the gain is maximized
# if player == 2nd player,
# gain = 0 + minimax(..., 1st player), where the gain is minimized because the 2nd player tries to maximize this

# TLE for this input without@lru_cache
# [8270,7145,575,5156,5126,2905,8793,7817,5532,5726,7071,7730,5200,5369,5763,7148,8287,9449,7567,4850,1385,2135,1737,9511,8065,7063,8023,7729,7084,8407]
