Solution: Stone Game VII

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #1690 (Medium): Stone Game VII

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

Examples:

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

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

Like most of the Stone Game problems, this one boils down to a system of ever-repeating subproblems, as the there are many different ways to get to the same board condition as we move towards the end of the game. This naturally points to a dynamic programming (DP) solution.

In order to represent the different board positions, we'd normally build an N * N DP matrix where N is the length of the stones array (S). In this DP array, dp[i][j] would represent the best score difference with i representing the leftmost remaining stone's index and j representing the rightmost remaining stone's index.

We'll start at i = N - 2 and iterate backwards and start each nested for loop at j = i + 1. This ensures that we're building the pyramid of DP results downward, always starting each row with i and j next to each other.

For each row, we'll keep track of the sum total of the stones in the range [i,j] by adding S[j] at each iteration of j. Then, we can represent the current player's ideal play by choosing the best value between picking the stone at i (total - S[i]) and picking the stone at j (total - S[j]). For each option, we have to also subtract the best value that the other player will get from the resulting board position (dp[i+1][j] or dp[i][j-1]).

Since we will only be building off the cells to the left and above the current cell, however, we can actually eliminate the DP matrix and instead just one array representing the current row, reusing it each time. This will drop the space complexity from O(N^2) to O(N).

This approach works because, when evaluating a new cell, the cell to the left will already have been overwritten and will accurately represent the previous cell on the same row. The not-yet-overwritten current cell value still represents the cell that would have been in the row above in a full DP matrix.

At the end, the solution will be the value stored in the DP array representing the board position with all stones present. We should therefore return dp[N-1].

• Time Complexity: O(N^2) where N is the length of S
• Space Complexity: O(N) for dp

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var stoneGameVII = function(S) {
    let N = S.length, dp = new Uint32Array(N)
    for (let i = N - 2; ~i; i--) {
        let total = S[i]
        for (let j = i + 1; j < N; j++) {
            total += S[j]
            dp[j] = Math.max(total - S[i] - dp[j], total - S[j] - dp[j-1])
        }
    }
    return dp[N-1]
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def stoneGameVII(self, S: List[int]) -> int:
        N, dp = len(S), [0] * len(S)
        for i in range(N - 2, -1, -1):
            total = S[i]
            for j in range(i + 1, N):
                total += S[j]
                dp[j] = max(total - S[i] - dp[j], total - S[j] - dp[j-1])
        return dp[-1]

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int stoneGameVII(int[] S) {
        int N = S.length;
        int[] dp = new int[N];
        for (int i = N - 2; i >= 0; i--) {
            int total = S[i];
            for (int j = i + 1; j < N; j++) {
                total += S[j];
                dp[j] = Math.max(total - S[i] - dp[j], total - S[j] - dp[j-1]);
            }
        }
        return dp[N-1];
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int stoneGameVII(vector<int>& S) {
        int N = S.size();
        vector<int> dp(N);
        for (int i = N - 2; ~i; i--) {
            int total = S[i];
            for (int j = i + 1; j < N; j++) {
                total += S[j];
                dp[j] = max(total - S[i] - dp[j], total - S[j] - dp[j-1]);
            }
        }
        return dp[N-1];
    }
};