Watch 10 video solutions for Stone Game VII, a medium level problem involving Array, Math, Dynamic Programming. This walkthrough by Pepcoding has 4,354 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Alice and Bob take turns playing a game, with Alice starting first.
There are n stones arranged in a row. On each player's turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones' values in the row. The winner is the one with the higher score when there are no stones left to remove.
Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score's difference. Alice's goal is to maximize the difference in the score.
Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob's score if they both play optimally.
Example 1:
Input: stones = [5,3,1,4,2] Output: 6 Explanation: - 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
Constraints:
n == stones.length2 <= n <= 10001 <= stones[i] <= 1000Problem Overview: You are given an array where each value represents a stone. Two players remove a stone from either end of the row. Instead of gaining the removed stone's value, the player gains the sum of the remaining stones. Both players play optimally, and the goal is to compute the maximum difference in score between Alice and Bob.
Approach 1: Dynamic Programming with Pre-computed Prefix Sum (O(n²) time, O(n²) space)
This approach models the game as a classic interval dynamic programming problem. Define dp[i][j] as the maximum score difference the current player can achieve from the subarray stones[i..j]. When a player removes the left stone, the gained score equals the sum of the remaining stones (i+1..j). If the right stone is removed, the gained score equals the sum of (i..j-1). Use a prefix sum array so range sums are computed in O(1). The recurrence becomes dp[i][j] = max(sum(i+1..j) - dp[i+1][j], sum(i..j-1) - dp[i][j-1]). Iterate over subarray lengths from small to large so smaller states are solved first. This produces the optimal score difference for the full interval dp[0][n-1]. The algorithm runs in O(n²) time because every pair (i, j) is evaluated once.
Approach 2: Recursive with Memoization (O(n²) time, O(n²) space)
The same recurrence can be expressed using recursion with memoization. Define a recursive function solve(i, j) representing the best score difference achievable from the interval [i, j]. At each step, simulate removing the left or right stone, compute the resulting score using prefix sums, and subtract the opponent's optimal response returned by the recursive call. Memoize results in a 2D cache so each state is computed once. Without memoization the recursion explores exponential game paths, but caching reduces it to O(n²). This approach mirrors the logic of optimal play in game theory problems and is often easier to reason about before converting to bottom‑up DP.
Recommended for interviews: The bottom‑up DP with prefix sums is the expected solution. It shows you recognize the interval DP pattern and can optimize repeated sum calculations. Starting with the recursive memoized version helps demonstrate understanding of optimal substructure and competitive decision making before translating it into an iterative DP table over the array.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Prefix Sum | O(n²) | O(n²) | Best general solution. Efficient for constraints up to several thousand elements. |
| Recursive with Memoization | O(n²) | O(n²) | Useful for understanding the game strategy and deriving the DP recurrence. |