石子游戏 VII

难度: Medium

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中，可以从行中移除最左边的石头或最右边的石头，并获得与该行中剩余石头值之和相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

示例 1：

输入：stones = [5,3,1,4,2]
输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。

示例 2：

输入：stones = [7,90,5,1,100,10,10,2]
输出：122

提示：

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

Submission

运行时间: 610 ms

内存: 16.0 MB

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        dp = list(stones)
        for j, acc in enumerate(stones):
            for i in range(j - 1, -1, -1):
                acc += stones[i]
                dp[i] = acc - (dp[i + 1] if dp[i + 1] > dp[i] else dp[i])
        return acc - dp[0]

Explain

该题解采用了动态规划的方法。dp[i] 表示从石头 i 到当前考虑的石头 j 的区间内，当前玩家与另一玩家的得分差的最大值。在每一轮中，玩家可以选择移除最左边或最右边的石头，然后更新 dp[i] 为剩余石头的总和减去 dp[i+1]（如果移除左边石头）和 dp[i]（如果移除右边石头）中的较大值，以保持得分差最大化。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        dp = list(stones)  # 初始化动态规划数组
        for j, acc in enumerate(stones):
            for i in range(j - 1, -1, -1):
                acc += stones[i]  # 更新剩余石头的总和
                # 更新 dp[i] 为剩余石头总和减去移除一端后的最大得分差
                dp[i] = acc - (dp[i + 1] if dp[i + 1] > dp[i] else dp[i])
        return acc - dp[0]  # 返回最终得分差

Explore

题解中将动态规划数组`dp`的初始值设置为`stones`数组本身，这是因为在只有一个石头的情况下，如果一个玩家选择了它，那么这个玩家的得分差相对于对手就是0（因为没有剩余的石头可以给对手得分）。因此，当考虑只有一个石子的情况时，得分差是0，这也是`dp`数组初始化为`stones`的理由。在后续的迭代中，这个初始值将被更新以表示更大区间的最优得分差。

状态转移方程`dp[i] = acc - (dp[i + 1] if dp[i + 1] > dp[i] else dp[i])`用于计算从石头i到j的区间内，当前玩家与对手的最大得分差。这里，`acc`是从石头i到j的石头总和，`dp[i+1]`和`dp[i]`分别代表移除左边或右边石头后的得分差。当前玩家会选择一个操作使得对手在下一步的得分差最小化，从而确保自己的得分差最大化。这种策略是一种典型的min-max策略，用于在对抗性游戏中确保一方的最优结果。

`acc`在代码中表示的是整个`stones`数组的总和，即所有石头的总和。最后返回`acc - dp[0]`是因为`dp[0]`在最终的迭代中表示的是从第一个石头到最后一个石头的最大得分差，而`acc`表示所有石头的总分。因此，`acc - dp[0]`表示在两个玩家都采取最优策略的情况下，最先操作的玩家可以达到的最大得分差。

在动态规划解法中，倒序更新`i`从`j-1`到`0`是为了确保在计算`dp[i]`时，所需要的`dp[i+1]`已经被正确计算和更新过。如果我们正序更新`i`，则在计算`dp[i]`时，`dp[i+1]`可能尚未更新，导致依赖的数据不正确。倒序更新保证了在更新某个`dp[i]`的值之前，其依赖的所有后续值已经是最新的，从而保证了动态规划状态的正确转移。