1690. Stone Game VII #

Problem #

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

Problem Summary #

In the stone game, Alice and Bob take turns, 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 values of the remaining stones in the row. When there are no stones left to remove, the player with the higher score wins. Bob found that he will always lose this game (poor Bob, he always loses), so he decides to minimize the score difference as much as possible. Alice’s goal is to maximize the score difference.

Given an integer array stones, where stones[i] represents the value of the i-th stone from the left, return the difference in their scores if both Alice and Bob play optimally.

Solution Ideas #

First consider what it means for Bob to reduce the score difference: it means he wants the relative score between himself and Alice to be as small as possible. Since it is already clear that Bob will definitely lose, his score must be lower than Alice’s, so Bob - Alice must be negative. The smaller the relative score, the larger the difference. The larger the negative number, the smaller the difference. Between -50 and -10, -10 is numerically larger and the difference is smaller. Therefore, Bob’s move is to make the relative score as large as possible. Alice’s goal is also this: to make Alice - Bob as large as possible, which here means making the positive number larger. In summary, both players have the same goal: to maximize the relative score.

Define dp[i][j] as the maximum score difference obtainable in the current interval stone[i ~ j]. The state transition equation is:

dp[i][j] = max(
                sum(i + 1, j) - dp[i + 1][j],   // Remove `stone[i]` this turn and gain sum(i + 1, j) points, then subtract the score the opponent can obtain from the remaining stones; this is the maximum score difference obtainable this turn.
                sum(i, j - 1) - dp[i][j - 1]    // Remove `stone[j]` this turn and gain sum(i, j - 1) points, then subtract the score the opponent can obtain from the remaining stones; this is the maximum score difference obtainable this turn.
              )

Compute sum(i + 1, j) = stone[i + 1] + stone[i + 2] + …… + stone[j] using prefix sums to calculate interval sums.

Solution 2 is code derived from the normal line of thinking. Solution 1 compresses the DP array; during the DP state transition, generating the next dp[j] actually follows a pattern. This pattern can be used to store one less dimension of data and compress the space. The code for Solution 1 is relatively hard to come up with directly. First write the code for Solution 2, then find the recurrence pattern, optimize the space by compressing it to one dimension, and then write the code for Solution 1.

Code #

package leetcode

// Solution 1: space-optimized DP
func stoneGameVII(stones []int) int {
	n := len(stones)
	sum := make([]int, n)
	dp := make([]int, n)
	for i, d := range stones {
		sum[i] = d
	}
	for i := 1; i < n; i++ {
		for j := 0; j+i < n; j++ {
			if (n-i)%2 == 1 {
				d0 := dp[j] + sum[j]
				d1 := dp[j+1] + sum[j+1]
				if d0 > d1 {
					dp[j] = d0
				} else {
					dp[j] = d1
				}
			} else {
				d0 := dp[j] - sum[j]
				d1 := dp[j+1] - sum[j+1]
				if d0 < d1 {
					dp[j] = d0
				} else {
					dp[j] = d1
				}
			}
			sum[j] = sum[j] + stones[i+j]
		}
	}
	return dp[0]
}

// Solution 2: conventional DP
func stoneGameVII1(stones []int) int {
	prefixSum := make([]int, len(stones))
	for i := 0; i < len(stones); i++ {
		if i == 0 {
			prefixSum[i] = stones[i]
		} else {
			prefixSum[i] = prefixSum[i-1] + stones[i]
		}
	}
	dp := make([][]int, len(stones))
	for i := range dp {
		dp[i] = make([]int, len(stones))
		dp[i][i] = 0
	}
	n := len(stones)
	for l := 2; l <= n; l++ {
		for i := 0; i+l <= n; i++ {
			dp[i][i+l-1] = max(prefixSum[i+l-1]-prefixSum[i+1]+stones[i+1]-dp[i+1][i+l-1], prefixSum[i+l-2]-prefixSum[i]+stones[i]-dp[i][i+l-2])
		}
	}
	return dp[0][n-1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}