#1690

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Stone Game VII

Maximize score difference in a two-player turn-based stone removal game using state transition dynamic programming.

array math dynamic programming game theory

Problem Statement

Alice and Bob play a game with a row of n stones. On each turn, a player removes either the leftmost or rightmost stone and earns points equal to the sum of the remaining stones. The game ends when no stones remain, and the player with the higher score wins.

Alice aims to maximize the score difference while Bob tries to minimize it. Implement a function that, given the initial array of stone values, returns the maximum difference Alice can achieve assuming both players play optimally.

Examples

Example 1

Input: stones = [5,3,1,4,2]

Output: 6

Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = []. The score difference is 18 - 12 = 6.

Example 2

Input: stones = [7,90,5,1,100,10,10,2]

Output: 122

Example details omitted.

Constraints

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

Solution Approach

Precompute Prefix Sums

Calculate prefix sums of the stones array to quickly compute the sum of any subarray in constant time. This enables efficient computation of points earned after removing a stone on either end.

Dynamic Programming State Definition

Define dp[i][j] as the maximum score difference the current player can achieve for the subarray stones[i..j]. Transition using dp[i+1][j] and dp[i][j-1] combined with the remaining sum after removing left or right stones.

Iterative DP Filling

Fill the DP table for increasing subarray lengths, ensuring smaller subproblems are solved first. The final result is dp[0][n-1], representing the maximum difference Alice can achieve for the entire array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to filling an n x n DP table and computing transitions in constant time using prefix sums. Space complexity is O(n^2) for the DP table, reducible to O(n) with optimization since only adjacent subarray results are needed at each step.

What Interviewers Usually Probe

Candidate immediately considers DP subarray state transitions.
Candidate tries a naive greedy approach and needs redirection to subarray sums.
Candidate correctly identifies that prefix sums optimize repeated sum computations.

Common Pitfalls or Variants

Common pitfalls

Forgetting to subtract the removed stone from the remaining sum when computing points.
Incorrectly defining dp state leading to miscounted score differences.
Overlooking base cases for single-stone subarrays.

Follow-up variants

Allow players to remove up to k stones from either end per turn.
Modify scoring so removed stone values are added instead of remaining sums.
Extend to three players with cyclic turns and maximize score difference for first player.

FAQ

What is the best approach for Stone Game VII?

Use state transition dynamic programming with prefix sums to compute maximum score difference efficiently.

Can Stone Game VII be solved using recursion alone?

Recursion without memoization is too slow; memoization or iterative DP is required for n up to 1000.

How are points calculated when removing a stone?

Points equal the sum of the remaining stones after removing either the leftmost or rightmost stone.

Why use prefix sums in Stone Game VII?

Prefix sums allow O(1) calculation of remaining subarray sums, avoiding repeated O(n) summations per move.

What common mistakes occur with state transition DP in this problem?

Misdefining dp[i][j] or failing to account for opponent's minimizing strategy often leads to incorrect maximum differences.

terminal

Solution

Solution 1: Memorization Search

First, we preprocess to get the prefix sum array $s$, where $s[i]$ represents the total sum of the first $i$ stones.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i > j:
                return 0
            a = s[j + 1] - s[i + 1] - dfs(i + 1, j)
            b = s[j] - s[i] - dfs(i, j - 1)
            return max(a, b)

        s = list(accumulate(stones, initial=0))
        ans = dfs(0, len(stones) - 1)
        dfs.cache_clear()
        return ans

Solution 2: Dynamic Programming

We can convert the memoization search in Solution 1 into dynamic programming. We define $f[i][j]$ as the score difference between the first and second players when the remaining stones are $stones[i], stones[i + 1], \dots, stones[j]$. Therefore, the answer is $f[0][n - 1]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i > j:
                return 0
            a = s[j + 1] - s[i + 1] - dfs(i + 1, j)
            b = s[j] - s[i] - dfs(i, j - 1)
            return max(a, b)

        s = list(accumulate(stones, initial=0))
        ans = dfs(0, len(stones) - 1)
        dfs.cache_clear()
        return ans

Continue Practicing

#1728 cat and mouse ii #1563 stone game v #1872 stone game viii