'''
Description: 
Autor: Au3C2
Date: 2020-12-29 16:13:04
LastEditors: Au3C2
LastEditTime: 2020-12-29 16:13:32
'''
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        length = len(piles)
        sum_piles = 0
        dp = [[0] * (length+1) for _ in range(length)]
        for i in range(length-1,-1,-1):
            sum_piles += piles[i]
            for m in range(1,length+1):
                if i+2*m >= length:
                    dp[i][m] = sum_piles
                else:
                    for x in range(1,2*m+1):
                        dp[i][m] = max(dp[i][m],sum_piles-dp[i+x][max(m,x)])
        return dp[0][1]

# 动态规划，中等
# https://leetcode-cn.com/problems/stone-game-ii/