877. 石子游戏

一、877. 石子游戏 1.1、题目描述

1.2.1、动态规划

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        #  f(i,j)表示对于下标 i 到下标j的(j−i+1)堆石子,当前选手相对于对手能够多出的石子数。
        dp = [[0]*n for _ in range(n)]
        
        # 若 i==j，则明显当前选手相对于对手多出的石子数为f(i,j)=piles[i],因为只有一堆石子。
        for i in range(n):
            dp[i][i] = piles[i]
            
        # 当亚历克斯拿了最左边下标为 i 的石子后，亚历克斯和李的石子数之差为 piles[i] - dp[i+1][j], 
        # 当亚历克斯拿了最右边下标为j的那堆石子后，亚历克斯和李的石子数之差为 piles[j] - dp[i][j-1], 取其中较大者为新的最优解。
        for j in range(1, n):
            for i in range(j-1, -1, -1):
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        
        return dp[0][n-1] > 0