Stone Game VII

MEDIUM

Description

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 i^th 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.length
2 <= n <= 1000
1 <= stones[i] <= 1000

Approaches

Checkout 4 different approaches to solve Stone Game VII. Click on different approaches to view the approach and algorithm in detail.

Space-Optimized Bottom-Up Dynamic Programming

This approach optimizes the space complexity of the bottom-up DP solution. By observing the state transitions, we can see that to compute the values for a subarray of a certain length, we only need the results for subarrays of the immediately smaller length. This means to compute the current row i of our DP table, we only need the next row i+1. This dependency allows us to reduce the space from O(n^2) to O(n).

Algorithm

Create a prefix sum array for O(1) sum calculations.
Create a 1D DP array dp[n], initialized to 0.
Iterate the start index i from n-2 down to 0.
In the inner loop, iterate the end index j from i+1 up to n-1.
Inside the inner loop, calculate the two possible differences: a. diff1 = (prefixSum[j+1] - prefixSum[i+1]) - dp[j]. Here dp[j] holds the value from the previous outer loop, which corresponds to dp[i+1][j]. b. diff2 = (prefixSum[j] - prefixSum[i]) - dp[j-1]. Here dp[j-1] holds the value just computed in the current inner loop, which corresponds to dp[i][j-1].
Update dp[j] with max(diff1, diff2).
After the loops, dp[n-1] will contain the result for the entire array stones[0...n-1].

The recurrence is dp[i][j] = max(sum(i+1, j) - dp[i+1][j], sum(i, j-1) - dp[i][j-1]). Let's iterate by the starting index i from n-2 down to 0, and the ending index j from i+1 up to n-1. When we compute dp[i][j], we need dp[i+1][j] (from the 'next' row i+1) and dp[i][j-1] (from the 'current' row i, but a previous column). This structure allows for space optimization. We can use a 1D array, say dp[n]. Let dp[j] represent the value for the current row i and column j. When we are calculating the row for i, the dp array will hold the values from the previous iteration, which corresponds to row i+1. The recurrence becomes: dp[j] = max(sum(i+1, j) - dp[j], sum(i, j-1) - dp[j-1]), where we update the dp array in place.

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }

        int[] dp = new int[n];

        // i is the starting index of the subarray
        for (int i = n - 2; i >= 0; i--) {
            // j is the ending index of the subarray
            for (int j = i + 1; j < n; j++) {
                // Sum of stones from i+1 to j
                int sumTakeLeft = prefixSum[j + 1] - prefixSum[i + 1];
                // Sum of stones from i to j-1
                int sumTakeRight = prefixSum[j] - prefixSum[i];

                // dp[j] currently holds dp[i+1][j] from the previous outer loop iteration
                // dp[j-1] holds dp[i][j-1] from the current inner loop iteration
                int diff1 = sumTakeLeft - dp[j];
                int diff2 = sumTakeRight - dp[j - 1];

                dp[j] = Math.max(diff1, diff2);
            }
        }

        return dp[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n^2). The nested loops run O(n^2) times, and each step is O(1).Space Complexity: O(n). We use a 1D array `dp` of size `n` and a prefix sum array of size `n+1`.

Pros and Cons

Pros:

Most efficient in terms of space complexity.
Maintains the optimal O(n^2) time complexity.

Cons:

The logic for in-place updates and loop directions can be tricky to reason about compared to the O(n^2) space solution.

Code Solutions

Checking out 3 solutions in different languages for Stone Game VII. Click on different languages to view the code.

class Solution {
private
  int[] s;
private
  Integer[][] f;
public
  int stoneGameVII(int[] stones) {
    int n = stones.length;
    s = new int[n + 1];
    f = new Integer[n][n];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + stones[i];
    }
    return dfs(0, n - 1);
  }
private
  int dfs(int i, int j) {
    if (i > j) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int a = s[j + 1] - s[i + 1] - dfs(i + 1, j);
    int b = s[j] - s[i] - dfs(i, j - 1);
    return f[i][j] = Math.max(a, b);
  }
}

Video Solution

Watch the video walkthrough for Stone Game VII

Patterns:

MathDynamic ProgrammingGame Theory

Data Structures:

Array

Companies:

Dunzo |