'''
Description: 
Autor: Au3C2
Date: 2020-12-29 21:01:44
LastEditors: Au3C2
LastEditTime: 2021-01-04 11:11:54
'''
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        length = len(stones)
        for i in range(1,length):            
            stones[i]+=stones[i-1]        
        dp = [[0] * length for _ in range(length)]      
        for i in range(length - 2, -1, -1):
            for j in range(i + 1, length):
                dp[i][j] = max(stones[j]-stones[i] - dp[i + 1][j], stones[j-1]-(stones[i-1] if i>0 else 0) - dp[i][j - 1])
        return dp[0][length - 1]   
    
# 动态规划，中等。好难啊
# https://leetcode-cn.com/problems/stone-game-vii/