Stone Game VII

Intuition

When a player faces the subarray from index i to index j, the score they gain from a move is the sum of whatever remains, so precomputing prefix sums lets us get any range total instantly. Define dp[i][j] as the best achievable score margin (current player minus opponent) when only stones i..j are left. If the current player removes stones[i], they immediately earn the sum of i+1..j and then the opponent plays optimally on that smaller range, contributing negatively as dp[i+1][j]. Removing stones[j] symmetrically earns the sum of i..j-1 minus dp[i][j-1]. The player picks whichever option yields the larger margin, so dp[i][j] is the maximum of those two choices. Building this table from the shortest ranges upward gives dp[0][n-1], the margin under optimal play by both sides.

Algorithm walkthrough

1. 1Build a prefix-sum array so the total of any range i..j is prefix[j + 1] - prefix[i] in constant time.
2. 2Initialize dp[i][i] = 0 because a single remaining stone forces a removal that leaves nothing to score.
3. 3Iterate over increasing range lengths so that smaller subranges are solved before larger ones.
4. 4For a range i..j, compute removing the left stone: (sum of i+1..j) - dp[i+1][j].
5. 5Compute removing the right stone: (sum of i..j-1) - dp[i][j-1], then set dp[i][j] to the larger of the two.
6. 6Return dp[0][n-1], the optimal score difference for the full row.

Implementation

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        dp = [[0] * n for _ in range(n)]
        for length in range(2, n + 1):
            for i in range(0, n - length + 1):
                j = i + length - 1
                take_left = (prefix[j + 1] - prefix[i + 1]) - dp[i + 1][j]
                take_right = (prefix[j] - prefix[i]) - dp[i][j - 1]
                dp[i][j] = max(take_left, take_right)
        return dp[0][n - 1]