1690. Stone Game v I I

# 1690. Stone Game VII#

## 题目 #

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`

## 解题思路 #

• 首先考虑 Bob 缩小分值差距意味着什么，意味着他想让他和 Alice 相对分数最小。Bob 已经明确肯定是输，所以他的分数一定比 Alice 小，那么 Bob - Alice 分数相减一定是负数。相对分数越小，意味着差值越大。负数越大，差值越小。-50 和 -10，-10 数值大，相差小。所以 Bob 的操作是让相对分数越大。Alice 的目的也是这样，要让 Alice - Bob 的相对分数越大，这里是正数的越大。综上，两者的目的相同，都是让相对分数最大化。

• 定义 `dp[i][j]` 代表在当前 `stone[i ~ j]` 区间内能获得的最大分差。状态转移方程为：

``````dp[i][j] = max(
sum(i + 1, j) - dp[i + 1][j],   // 这一局取走 `stone[i]`，获得 sum(i + 1, j) 分数，再减去剩下对手能获得的分数，即是此局能获得的最大分差。
sum(i, j - 1) - dp[i][j - 1]    // 这一局取走 `stone[j]`，获得 sum(i, j - 1) 分数，再减去剩下对手能获得的分数，即是此局能获得的最大分差。
)
``````

计算 `sum(i + 1, j) = stone[i + 1] + stone[i + 2] + …… + stone[j]` 利用前缀和计算区间和。

• 解法二是正常思路解答出来的代码。解法一是压缩了 DP 数组，在 DP 状态转移的时候，生成下一个 `dp[j]` 实际上是有规律的。利用这个规律可以少存一维数据，压缩空间。解法一的代码直接写出来，比较难想。先写出解法二的代码，然后找到递推规律，优化空间压缩一维，再写出解法一的代码。

## 代码 #

``````package leetcode

// 解法一 优化空间版 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]
}

// 解法二 常规 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
}
``````

Apr 8, 2023