1690. Stone Game VII - cocoder39/coco39_LC GitHub Wiki

1690. Stone Game VII

dp[i][j]: Given stones[i ... j] as the remaining piles, dp[i][j] is the max diff current player can make. Each player is trying to maximize dp[i][j] at his/her turn

dp[i][j] = max(t - stones[i] - dp[i+1][j], t - stones[j] - dp[i][j-1])

• if current player picks i, then he can get t - stones[i], next player will gain max diff dp[i+1][j]. So the diff gained by current player is t - stones[i] - dp[i+1][j]

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        
        total = [0] * n
        for i in range(n):
            if i == 0:
                total[i] = stones[i]
            else:
                total[i] = total[i-1] + stones[i]
        
        dp = [[0] * n for i in range(n)]
        
        for k in range(2, n+1):
            for i in range(n-k+1):
                j = i + k - 1
                t = total[j] - (total[i-1] if i >= 1 else 0)
                dp[i][j] = max(t - stones[i] - dp[i+1][j], t - stones[j] - dp[i][j-1])
        return dp[0][n-1]