877. Stone Game - cocoder39/coco39_LC GitHub Wiki

877. Stone Game

dp[i][j] is the max diff between current player and the next player if currently only piles[i] to piles[j] are available

• If i == j, then there is only one pile so current player is piles[i] and next player is 0
• dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
  • if current player picks piles[i], then the max diff he can get is piles[i] - (the max diff the next player can gain with piles[i+1 ... j] available)

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for i in range(n)] # dp[i][j] is the max delta between current player and the next player
        
        for i in range(n):
            dp[i][i] = piles[i]
            
        for k in range(2, n+1):
            for i in range(n-k+1):
                j = i + k - 1
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        
        return dp[0][n-1] > 0