Code Implementation

class Solution:
    def stoneGameVII(self, stones):
        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(n - length + 1):
                j = i + length - 1
                score_remove_left = prefix[j+1] - prefix[i+1] - dp[i+1][j]
                score_remove_right = prefix[j] - prefix[i] - dp[i][j-1]
                dp[i][j] = max(score_remove_left, score_remove_right)
        return dp[0][n-1]
      

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<int> prefix(n+1, 0);
        for (int i = 0; i < n; ++i)
            prefix[i+1] = prefix[i] + stones[i];
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                int score_left = prefix[j+1] - prefix[i+1] - dp[i+1][j];
                int score_right = prefix[j] - prefix[i] - dp[i][j-1];
                dp[i][j] = max(score_left, score_right);
            }
        }
        return dp[0][n-1];
    }
};
      

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefix = new int[n+1];
        for (int i = 0; i < n; i++) {
            prefix[i+1] = prefix[i] + stones[i];
        }
        int[][] dp = new int[n][n];
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                int left = prefix[j+1] - prefix[i+1] - dp[i+1][j];
                int right = prefix[j] - prefix[i] - dp[i][j-1];
                dp[i][j] = Math.max(left, right);
            }
        }
        return dp[0][n-1];
    }
}
      

var stoneGameVII = function(stones) {
    const n = stones.length;
    const prefix = new Array(n+1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i+1] = prefix[i] + stones[i];
    }
    const dp = Array.from({length: n}, () => new Array(n).fill(0));
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {
            let j = i + len - 1;
            let left = prefix[j+1] - prefix[i+1] - dp[i+1][j];
            let right = prefix[j] - prefix[i] - dp[i][j-1];
            dp[i][j] = Math.max(left, right);
        }
    }
    return dp[0][n-1];
};
      

Problem Description

In the Stone Game VII problem, you are given an array stones of integers, where each element represents the value of a stone in a row. Two players take turns removing a stone from either the beginning or end of the row. After each removal, the player gains points equal to the sum of the remaining stones. The game continues until there are no stones left.

Both players play optimally, and your task is to return the difference in scores between the two players at the end of the game (i.e., score of player 1 - score of player 2), assuming player 1 starts first.

• Only the sum of the remaining stones is added to the current player's score after each move.
• Each stone can only be removed once.
• Both players play optimally to maximize their own score difference.
• 1 <= stones.length <= 1000
• 1 <= stones[i] <= 1000

Thought Process

At first glance, it might seem reasonable to try all possible sequences of moves and track the scores for both players. However, with up to 1000 stones, the number of possible move sequences grows exponentially. A brute-force approach would quickly become infeasible.

To improve, we notice that the game has overlapping subproblems: the state of the game at any point can be described by the current subarray of stones, and the optimal move depends only on this state. This suggests that dynamic programming (DP) can be used to avoid recomputation.

The key insight is to realize that, at every step, the current player can choose to remove the leftmost or rightmost stone, and the rest of the problem reduces to a smaller subproblem. We need to carefully model the score difference and ensure that both players are playing optimally.

Solution Approach

• State Representation:
  • Let dp[i][j] represent the maximum difference in scores the current player can achieve over the opponent, considering only stones from index i to j (inclusive).
• Base Case:
  • If i == j, there are no stones left to remove, so the difference is 0: dp[i][j] = 0.
• Transition:
  • For each move, the current player can:
    • Remove the leftmost stone (i): The sum of remaining stones is sum(stones[i+1..j]).
    • Remove the rightmost stone (j): The sum of remaining stones is sum(stones[i..j-1]).
  • After removing a stone, the opponent will play optimally, so we subtract the result of the subproblem from the current gain:
    • score_remove_left = total(i+1, j) - dp[i+1][j]
    • score_remove_right = total(i, j-1) - dp[i][j-1]
  • The current player chooses the move that maximizes their score difference:
    • dp[i][j] = max(score_remove_left, score_remove_right)
• Prefix Sum Optimization:
  • To quickly compute the sum of any subarray stones[i..j], we use a prefix sum array.
• Bottom-Up DP:
  • We fill the dp table for increasing subarray lengths, starting from length 2 up to n.
• Final Answer:
  • The answer is dp[0][n-1], representing the optimal score difference for the entire array.

Example Walkthrough

Let's work through an example: stones = [5, 3, 1, 4, 2]

1. Initial State: The sum is 15. Player 1 can remove 5 (left) or 2 (right).
   • If player 1 removes 5: Remaining stones = [3,1,4,2], sum = 10. Player 1 gains 10.
   • If player 1 removes 2: Remaining stones = [5,3,1,4], sum = 13. Player 1 gains 13.
2. Next State: For each possibility, it's player 2's turn and they will also play optimally.
   • If player 1 removed 5, player 2 can remove 3 or 2. Each choice leads to a new subproblem.
   • If player 1 removed 2, player 2 can remove 5 or 4. Again, each is a new subproblem.
3. This process continues recursively, with each player's move reducing the problem to a smaller subarray and the DP table storing the best possible score difference from that state.
4. The DP table is filled in bottom-up order, so by the time we need dp[i+1][j] or dp[i][j-1], they are already computed.
5. After populating the table, dp[0][4] will hold the maximum difference player 1 can achieve over player 2. For this example, the answer is 6.

Time and Space Complexity

• Brute-force:
  • Trying all possible move sequences would lead to O(2^n) time complexity, which is infeasible for large n.
• Optimized DP Solution:
  • There are O(n^2) possible subarrays (dp[i][j] for all i <= j).
  • Each state is computed in O(1) time using prefix sums.
  • Total Time Complexity: O(n^2).
  • Space Complexity: O(n^2) for the DP table and O(n) for the prefix sum array.

Summary

The Stone Game VII problem is a classic example of using dynamic programming to solve a two-player game with optimal strategies. By representing the problem in terms of subarray intervals and using a DP table to store the optimal score difference for each interval, we avoid redundant calculations and achieve an efficient solution. The use of prefix sums allows for quick computation of subarray sums, and the bottom-up DP approach ensures that all necessary subproblems are solved before they're needed. This method transforms an exponential brute-force problem into a manageable quadratic solution.