1690. Stone Game VII

Problem Description

Alice and Bob play a game with n stones arranged in a row. Each player takes turns removing either the leftmost or rightmost stone. The player receives points equal to the sum of the remaining stones' values. The player with the higher score wins. The goal is to find the difference in Alice and Bob's scores if they both play optimally. Alice aims to maximize the difference, while Bob aims to minimize it.

Solution: Dynamic Programming

This problem can be solved efficiently using dynamic programming. We can build a solution bottom-up, starting with smaller subproblems and building up to the final solution.

Approach

1. Prefix Sum: Calculate the prefix sum of the stones array. The prefix sum s[i] represents the sum of stones from index 0 to i-1. This allows for efficient calculation of the sum of any subarray in O(1) time.

2. DP Table: Create a 2D DP table dp of size n x n, where dp[i][j] represents the maximum score difference Alice can achieve when playing optimally with the subarray stones[i...j].

3. Base Case: When i > j (empty subarray), the score difference is 0. Therefore, dp[i][j] = 0 for i > j.

4. State Transition: For a given subarray stones[i...j], Alice has two choices:

   • Remove stones[i]: Alice's score increases by the sum of the remaining stones (s[j+1] - s[i+1]). Bob then plays optimally on the remaining subarray stones[i+1...j], resulting in a score difference of s[j+1] - s[i+1] - dp[i+1][j].
   • Remove stones[j]: Alice's score increases by the sum of the remaining stones (s[j] - s[i]). Bob then plays optimally on the remaining subarray stones[i...j-1], resulting in a score difference of s[j] - s[i] - dp[i][j-1].

   Alice chooses the option that maximizes her score difference. Therefore:

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

5. Final Result: The final answer is dp[0][n-1].

Time and Space Complexity

• Time Complexity: O(n^2) due to the nested loops iterating through the DP table.
• Space Complexity: O(n^2) to store the DP table.

Code Implementation

Python

from itertools import accumulate
 
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        s = list(accumulate(stones, initial=0))  # Prefix sum
        dp = [[0] * n for _ in range(n)]
 
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = max(s[j + 1] - s[i + 1] - dp[i + 1][j], s[j] - s[i] - dp[i][j - 1])
 
        return dp[0][n - 1]

Java

import java.util.Arrays;
 
class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + stones[i];
        }
        int[][] dp = new int[n][n];
 
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Math.max(s[j + 1] - s[i + 1] - dp[i + 1][j], s[j] - s[i] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
}

C++

#include <vector>
#include <numeric>
 
using namespace std;
 
class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<long long> s(n + 1, 0);
        partial_sum(stones.begin(), stones.end(), s.begin() + 1);
        vector<vector<long long>> dp(n, vector<long long>(n, 0));
 
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = max(s[j + 1] - s[i + 1] - dp[i + 1][j], s[j] - s[i] - dp[i][j - 1]);
            }
        }
        return (int)dp[0][n - 1];
    }
};

These code examples implement the dynamic programming solution. The Python and Java solutions use simple array-based DP tables. The C++ solution uses vector for the DP table for better flexibility. All have the same O(n^2) time and space complexity. Remember to handle potential integer overflow if input numbers are very large.